Binary Tree Longest Consecutive Sequence

题目

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 is3-4-5, so return3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is2-3,not3-2-1, so return2.

思路分析

这道题有些类似于tree的path的问题，直观上来讲应该是用DFS来实现。首先是确定post order travese tree，也就是说先递归到树的最底部，然后向上backtracking，判断root的val跟它的左子树跟右子树的val。把每个节点上的longest consecutive跟result对比，如果比当前的result值大，就把这个值赋给result。然后DFS函数的返回值是什么呢，这个递归函数的返回值应该是当前节点的longest consecutive。

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    public int dfs(TreeNode root, int[] result){
        if(root == null) return 0;
        int left = dfs(root.left, result);
        int right = dfs(root.right, result);
        if (root.left!=null && root.val+1 == root.left.val) left++;
        else left = 1;
        if (root.right!=null && root.val+1 == root.right.val) right++;
        else right = 1;
        int curConse = left > right ? left : right;
        result[0] = Math.max(result[0], curConse);
        return curConse;
    }
}