549. Binary Tree Longest Consecutive Sequence II

Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

• For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.

On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input: root = [1,2,3]
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input: root = [2,1,3]
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].

• -3 * 104 <= Node.val <= 3 * 104

Solution

When we encounter a tree problem, it will likely use the recursive technique in most cases.

In this problem, we observe a consequence length starting from a node to its child node could be a decreasing or increasing case.

4 or 4 / \ 5 3 / \ 6 2 / \ 7 1

So that, we can find a consequence count of a node can be obtained by "increasing count + decreasing count - 1) which is form by node and its child nodes. The idea is to iterate all the nodes and repeatedly check its childern node's consequence count and update the max.

Given that the increasing/decreasing count of the node is base on the increasing/decreasing count of its children nodes. So we can come out with a recursive solution for this problem.

int max = 0;
public int longestConsecutive(TreeNode root){
    helper(root);
    return max;
}

//[0] : increasing count start from node
//[1] : decreasing count start from node
public 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){
            dec = left[1] + 1;
        }else if (node.val - node.left.val == -1){
            inc = left[0] + 1;
        }
    }
    if(node.right != null){
        int[] right = helper(node.right);
        if(node.val - node.right.val == 1){
            dec = Math.max(dec, right[1] + 1);
        }else if (node.val - node.right.val == -1){
            inc = Math.max(inc, right[0] + 1);
        }
    }
    
    max = Math.max(max, inc + dec -1);
    return new int[]{inc, dec};
}