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).
For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

這題是連續(xù)遞增序列就行，
solution_extra是考慮續(xù)遞遞增|續(xù)遞遞減的情況，
另外因為本題是parent-child，所以pre-order post-order都可以。

Solution：DFS

思路：dfs 并傳遞 當(dāng)前最大c_max_len_inc 和 上一個結(jié)點來做判斷從而更新當(dāng)前的c_max_len_inc，更新global result。

Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存

Solution Code：
//parent2child連續(xù)遞增序列

class Solution {
    private int result;
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        result = 1;
        dfsHelper(root, null, 1);
        return result;
    }
    
    private void dfsHelper(TreeNode node, TreeNode prev, int c_max_len_inc) {
        if(node == null) return;
        if(prev != null && node.val == prev.val + 1) {
            c_max_len_inc++;
            if(c_max_len_inc > result) result = c_max_len_inc;
        }
        else {
            c_max_len_inc = 1;
        }
        dfsHelper(node.left, node, c_max_len_inc);
        dfsHelper(node.right, node, c_max_len_inc);
    }
}

Extra: parent2child可以連續(xù)遞增|連續(xù)遞減序列

//傳遞也應(yīng)該寫成package比較clear
class Solution_extra {
    private int result;
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        result = 1;
        dfsHelper(root, null, 1, 1);
        return result;
    }
    
    private void dfsHelper(TreeNode node, TreeNode prev, int c_max_len_inc, int c_max_len_dec) {
        if(node == null) return;
        if(prev != null && node.val == prev.val + 1) {
            c_max_len_inc++;
            c_max_len_dec = 1;
            if(c_max_len_inc > result) result = c_max_len_inc;
        }
        else if(prev != null && node.val == prev.val - 1) {
            c_max_len_dec++;
            c_max_len_inc = 1;
            if(c_max_len_dec > result) result = c_max_len_dec;
        }
        else {
            c_max_len_inc = 1;
            c_max_len_dec = 1;
        }
        dfsHelper(node.left, node, c_max_len_inc, c_max_len_dec);
        dfsHelper(node.right, node, c_max_len_inc, c_max_len_dec);
    }
}