LeetCode 549: Binary Tree Longest Consecutive Sequence II

Explanation:

This problem asks us to find the longest consecutive sequence in a binary tree. The consecutive sequence can be either increasing or decreasing, but the nodes have to be in the same order as in the root-to-leaf paths.

To solve this problem, we can use a recursive approach where we pass the current node, the length of the increasing sequence ending at the current node, and the length of the decreasing sequence ending at the current node. At each node, we compare the node's value with its children to determine if we can extend the consecutive sequences.

Here are the steps for the algorithm:

1. Define a recursive function that takes the current node, the length of increasing sequence ending at the current node, and the length of decreasing sequence ending at the current node.
2. Base case: If the current node is null, return a pair of (0, 0) representing the length of increasing and decreasing sequences as 0.
3. Recursively call the function on the left and right children of the current node.
4. Determine if we can extend the increasing and decreasing sequences at the current node based on its value and the values of its children.
5. Update the maximum length of the consecutive sequence found so far.
6. Return a pair of the length of increasing sequence and the length of decreasing sequence ending at the current node.

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. The space complexity is O(N) as well for the recursive stack.

:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    int maxLen = 0;

    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return maxLen;
    }

    private int[] helper(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        int inc = 1, dec = 1;
        if (node.left != null) {
            int[] left = helper(node.left);
            if (node.val == node.left.val + 1)
                inc = left[0] + 1;
            else if (node.val == node.left.val - 1)
                dec = left[1] + 1;
        }
        if (node.right != null) {
            int[] right = helper(node.right);
            if (node.val == node.right.val + 1)
                inc = Math.max(inc, right[0] + 1);
            else if (node.val == node.right.val - 1)
                dec = Math.max(dec, right[1] + 1);
        }

        maxLen = Math.max(maxLen, inc + dec - 1);
        return new int[]{inc, dec};
    }
}