Share my DFS solution with global variable


  • 0
    A

    The idea is straight-forward: we recursively check each node its longest possible consecutive sequence length (the sequence that ends with this node) against the current max length. If the current node's left or right child is just one larger than its value, we keep increasing the sequence length and the final max after all the recursions is the largest possible value.

    int max = 0;
    
    public int longestConsecutive(TreeNode root) {
        dfs(root, 0);
        return max;
    }
    
    private void dfs(TreeNode node, int len) {
        if (node == null) return;
        len++;
        if (len > max) max = len;
        if (node.left != null) {
            if (node.left.val == node.val + 1) dfs(node.left, len);
            else dfs(node.left, 0);
        }
        if (node.right != null) {
            if (node.right.val == node.val + 1) dfs(node.right, len);
            else dfs(node.right, 0);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.