298. Binary Tree Longest Consecutive Sequence QuestionEditorial Solution

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.

2.算法
我一开始理解错题一了，我以为consecutive sequence可以从上往下看或者从下往上看。做了那个
这道题可以从任意点开始，因此每个点都有可能是答案。
postorder 或者preorder 都能做

 public class Solution {  
   public int max = 0;  
   public int longestConsecutive(TreeNode root) {  
     dfs(root);  
     return max;  
   }  
   public int dfs(TreeNode root) {  
     int ans = 0;  
     if(root == null)  
       return ans;  
     int left = dfs(root.left);  
     int right = dfs(root.right);  
     if(root.left!=null&&root.left.val == root.val+1)  
         ans = left+1;  
     if(root.right!=null&&root.right.val == root.val+1)  
         ans = Math.max(ans, right+1);  
     if(ans==0)  
       ans++;  
     // System.out.println(ans);  
     max = Math.max(ans, max);  
     return ans;  
   }  
 }  

如果是consecutive sequence可以从上往下看或者从下往上看:

 public int max = 0;  
   public int longestConsecutive(TreeNode root) {  
     dfs(root);  
     return max;  
   }  
   public int[] dfs(TreeNode root) {  
     //ans[0] is increasing number, ans[1] is decreasing number  
     int[] ans = new int[2];  
     if(root == null)  
       return ans;  
     int[] left = dfs(root.left);  
     if(root.left!=null){  
       if(root.left.val == root.val-1)  
         ans[0] = left[0];  
       if(root.left.val == root.val+1)  
         ans[1] = left[1];  
     }  
     int[] right = dfs(root.right);  
     if(root.right!=null){  
       if(root.right.val == root.val-1)  
         ans[0] = Math.max(ans[0], right[0]);  
       if(root.right.val == root.val+1)  
         ans[1] = Math.max(ans[1], right[1]);  
     }  
     ans[0]++;ans[1]++;  
     max = Math.max(max,Math.max(ans[1], ans[0]));  
     return ans;  
   }