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

Max Distance

这是一道GG电面题。
1.题意：给一个Unsorted array A，for all A[i] <= A[j]，求j-i的最大值。O(N) time, O(N) space.
http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/
2.算法：

这个题最简单的事O(N^2)解法，假设扫到index为j那个点的时候，最大distance为max在A[j]点找最小的i使得A[i] <= A[j]，这个i点从j-max-1开始。

HINT：Space是O(N)，可以用一个array存smallest so far

不能按照之前的思路走，因为之前的思路如果额外加一个smallest so far 的array并没有帮助，A[j]并不知道i是谁。

O(N)time 考虑two pointer。

用A[j]和smallest[j-max-1]比较

A[j]  >= smallest[j-max-1] 更新max=max+1
A[j]  < smallest[j-max-1] j--
j>j-max-1, j-max-1>=0 => j>=max+1
因此O(N)

 public int maxDistance(int[] nums){  
   int[] smallest = new int[nums.length];  
   int min = Integer.MAX_VALUE;  
   for(int i = 0; i < nums.length; i++){  
     if(nums[i] < min){  
       min = smallest[i];  
     }  
     smallest[i] = min;  
   }  
   int j = nums.length-1;  
   int max = 0;  
   while(j >=max+1){  
     while(nums[j] >= smallest[j-max-1]) max++;  
     j--;  
   }  
   return max;  
 }