437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

O(n^2)
每个点作为起点，遍历结果

    public int pathSum(TreeNode root, int sum) {
        if(root == null)
            return 0;
        return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    public int findPath(TreeNode root, int sum){
        int res = 0;
        if(root == null)
            return res;
        if(sum == root.val)
            res++;
        res += findPath(root.left, sum - root.val);
        res += findPath(root.right, sum - root.val);
        return res;
    }

O(nlogn)  记录<preSum,Count>并且对每个点在preSum Map里找(sum-target)的值，sum是从root下来的path的总和，如果对于当前位置而言，(sum-target)出现过那么sum-前面对应位置的sum就是target，也就是说这两个位置之间的和是target。 对于preSum记录count 就能找到多个位置满足(当前sum-target == preSum)。 思路是如果这个点是end point 的话，count要加。

255 Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:

Could you do it using only constant space complexity?

Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

维护一个单调递减的stack，当遇到递增的时候说明已经到了某个parent 的right subtree，并且不会在走比parent小的点，因此维护一个pre 值，来记录去right subtree之前的转折点。

  public boolean verifyPreorder(int[] preorder) {  
     Stack<Integer> desc = new Stack<>();  
     int pre = Integer.MIN_VALUE;  
     for(int i = 0; i < preorder.length; i++){  
       if(preorder[i] < pre) return false;  
       while(!desc.empty()&&preorder[i] > desc.peek()){  
           pre = desc.pop();  
       }  
       desc.push(preorder[i]);  
     }  
     return true;  
   }  

Solution 2 ... O(1) extra space

Same as above, but abusing the given array for the stack.

把preorder这个array当作stack来维护，用一个指针，如果是push，那么就是copy val到指针位置，并且向右移动指针，如果是pop 就像左移动指针。

public boolean verifyPreorder(int[] preorder) {
    int min = Integer.MIN_VALUE, i = -1;
    for (int val : preorder) {
        if (val < min)
            return false;
        while (i >= 0 && val > preorder[i])
            min = preorder[i--];
        preorder[++i] = val;
    }
    return true;
}

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