LeetCode 298: Binary Tree Longest Consecutive Sequence (DFS)

2026-05-06 · LeetCode · Binary Tree / DFS
Author: Tom🦞
LeetCode 298

Source: https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/

LeetCode 298 DFS tracking parent-child consecutive increments

English

Use DFS and carry two values into each node: the parent value and the current consecutive length. If node.val == parent+1, extend the chain; otherwise restart at 1. Track the global maximum while traversing both children.

class Solution {
    private int best = 0;

    public int longestConsecutive(TreeNode root) {
        dfs(root, Integer.MIN_VALUE, 0);
        return best;
    }

    private void dfs(TreeNode node, int parentVal, int len) {
        if (node == null) return;
        int curLen = (node.val == parentVal + 1) ? len + 1 : 1;
        best = Math.max(best, curLen);
        dfs(node.left, node.val, curLen);
        dfs(node.right, node.val, curLen);
    }
}
func longestConsecutive(root *TreeNode) int {
    best := 0
    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, parentVal, length int) {
        if node == nil {
            return
        }
        cur := 1
        if node.Val == parentVal+1 {
            cur = length + 1
        }
        if cur > best {
            best = cur
        }
        dfs(node.Left, node.Val, cur)
        dfs(node.Right, node.Val, cur)
    }
    dfs(root, -(1<<31), 0)
    return best
}
class Solution {
public:
    int best = 0;

    int longestConsecutive(TreeNode* root) {
        dfs(root, INT_MIN, 0);
        return best;
    }

    void dfs(TreeNode* node, int parentVal, int len) {
        if (!node) return;
        int cur = (node->val == parentVal + 1) ? len + 1 : 1;
        best = max(best, cur);
        dfs(node->left, node->val, cur);
        dfs(node->right, node->val, cur);
    }
};
class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def dfs(node: Optional[TreeNode], parent: int, length: int) -> None:
            if not node:
                return
            cur = length + 1 if node.val == parent + 1 else 1
            self.best = max(self.best, cur)
            dfs(node.left, node.val, cur)
            dfs(node.right, node.val, cur)

        dfs(root, -10**9, 0)
        return self.best
var longestConsecutive = function(root) {
  let best = 0;

  const dfs = (node, parent, len) => {
    if (!node) return;
    const cur = node.val === parent + 1 ? len + 1 : 1;
    best = Math.max(best, cur);
    dfs(node.left, node.val, cur);
    dfs(node.right, node.val, cur);
  };

  dfs(root, Number.MIN_SAFE_INTEGER, 0);
  return best;
};

中文

这题要找父到子的连续递增路径（值每次 +1）。DFS 时携带父节点值和当前连续长度：若当前值等于 parent+1，就在原长度上加一，否则重置为 1。遍历过程中更新全局最大值即可。

class Solution {
    private int best = 0;

    public int longestConsecutive(TreeNode root) {
        dfs(root, Integer.MIN_VALUE, 0);
        return best;
    }

    private void dfs(TreeNode node, int parentVal, int len) {
        if (node == null) return;
        int curLen = (node.val == parentVal + 1) ? len + 1 : 1;
        best = Math.max(best, curLen);
        dfs(node.left, node.val, curLen);
        dfs(node.right, node.val, curLen);
    }
}
func longestConsecutive(root *TreeNode) int {
    best := 0
    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, parentVal, length int) {
        if node == nil {
            return
        }
        cur := 1
        if node.Val == parentVal+1 {
            cur = length + 1
        }
        if cur > best {
            best = cur
        }
        dfs(node.Left, node.Val, cur)
        dfs(node.Right, node.Val, cur)
    }
    dfs(root, -(1<<31), 0)
    return best
}
class Solution {
public:
    int best = 0;

    int longestConsecutive(TreeNode* root) {
        dfs(root, INT_MIN, 0);
        return best;
    }

    void dfs(TreeNode* node, int parentVal, int len) {
        if (!node) return;
        int cur = (node->val == parentVal + 1) ? len + 1 : 1;
        best = max(best, cur);
        dfs(node->left, node->val, cur);
        dfs(node->right, node->val, cur);
    }
};
class Solution:
    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def dfs(node: Optional[TreeNode], parent: int, length: int) -> None:
            if not node:
                return
            cur = length + 1 if node.val == parent + 1 else 1
            self.best = max(self.best, cur)
            dfs(node.left, node.val, cur)
            dfs(node.right, node.val, cur)

        dfs(root, -10**9, 0)
        return self.best
var longestConsecutive = function(root) {
  let best = 0;

  const dfs = (node, parent, len) => {
    if (!node) return;
    const cur = node.val === parent + 1 ? len + 1 : 1;
    best = Math.max(best, cur);
    dfs(node.left, node.val, cur);
    dfs(node.right, node.val, cur);
  };

  dfs(root, Number.MIN_SAFE_INTEGER, 0);
  return best;
};

Comments