# 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:**![](https://assets.leetcode.com/uploads/2021/03/14/consec2-1-tree.jpg)

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

**Example 2:**![](https://assets.leetcode.com/uploads/2021/03/14/consec2-2-tree.jpg)

```
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.

&#x20;                  4                         or                         4\
&#x20;                 /                                                          \\\
&#x20;              5                                                               3\
&#x20;            /                                                                    \\\
&#x20;         6                                                                         2\
&#x20;       /                                                                              \\\
&#x20;    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.\\

```java
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};
}

```

\\
