# Binary Tree Longest Consecutive Sequence

<https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/description/>

> Given a binary tree, find the length of the longest consecutive sequence path.
>
> The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

## Thoughts

分治得到左子树中的最长和右子树的最长, 由于子树中的最长未必穿过左/右儿子但当前结点可能和左右儿子形成新的最长, 因此还要记录穿过当前节点最长. 有两种记录的方法, 一种bottom-up, 还有种up-bottom, 后者不需要全局变量.

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int helper(TreeNode root, int count, int val) {
        if (root == null) {
            return count;
        }
        count = (root.val - val) == 1 ? count + 1 : 1;
        int left = helper(root.left, count, root.val);
        int right = helper(root.right, count, root.val);
        return Math.max(Math.max(left, right), count);
    }

    public int longestConsecutive(TreeNode root) {
        return helper(root, 0, root == null ? 0 : root.val);
    }
}
```

## Analysis

时间复杂度O(N).