Tree Path

Botton-Up : related with DP

Top - Down: ..

Traps

1. 对获取的value定义不够严格。
   1. max path sum from non-leaf node to non-leaf node.
   2. max path sum from any node to any node
   3. max robber III.

How to avoid?

养成一个好习惯，定义function的时候，清楚的知道function的含义，return type的含义。(其实对于任何题目都是这样的).

Classical Questions

House Robber Question

不管多简单的题，也一定要step by step. 因为你也不知道哪里有坑：—）

Step 1: Understand the question.

two directly linked house can't rob at same time

In a BST, directly linked house means "parent and child".

Step 2：Divide and Conquer.

For each house,

1.rob current house :

max = max_not_rob_fromLeft + max_not_rob_fromRight + money_in_house

2.not_rob_current_house :

max = max (max_rob_fromLeft, max_not_rob_fromLeft) + max(max_rob_fromRight, max_not_rob_fromRight);

一个通过0,1选择来Divide and Conquer的例题。

1. 如果选择rob当前房子，globalMax 可以来自于?
2. 如果不rob，globalMax可以来自于无限制的左边最大，无限制的右边最大。

Return type:

tuple: [maxRob, max_not_rob]

Step 3: Talk is cheap, show me you code

public int rob(TreeNode root) {
     if (root == null) {
          return Integer.MIN_VALUE;
     }
     int[] ret = helper(root);
     return Math.max(ret[0],ret[1]);
}
//return type : [max_rob, max_not_rob]
private int[] helper(TreeNode root) {
    if (root == null) {
        return new int[2];
    }
    int[] fromLeft = helper(root.left);
    int[] fromRight = helper(root.right);
    int max_rob = fromLeft[1] + fromRight[1] + root.val;
    int max_not_rob = Math.max(fromLeft[0],fromLeft[1]) +  Math.max(fromRight[0],fromRight[1]);
    return new int[] {max_rob, max_not_rob};
}

Sum Root to Leaf Numbers

base case :

if use null, it hurts...a number is added twice.

所以在该停的时候，要停下来，如果follow一个非常正确的order，不会踩那么多坑。

Without changing parent to child relationship, make node on leftMost path.

           4                                 4
        /     \                            /  \
       2       5                         5     2
      / \   /     \                     / \   / \
     1   3  6(t)  7                    6  7  1  　3
           / \                        / \
          8   9                      8   9

~~Solution I: my solution

This is not right!!!! consider node 7.

step 1: fing leaf nodes on leftMost path. O(height). we say node L. (if target is on leftMost path, do nothing).

step 2: find LCA(L,target)

step 3 : swap LCA (left child, right child). ~~

Solution II: solution on docs (Divide and Conquer).

target on leftMost path, we say from root to target node, node should always go left. if on right path, swap left and right. (need to know parent position, indicator of using return bottom up value).

   //return type : is target on leftMost path rooted at root?
   public boolean leftMost(TreeNode root, TreeNode target) {
        if (root == null) {
            return false;
        }
        if (root == target) {
            return true;
        }
        boolean onLeft = leftMost(root.left, target);
        boolean onRight = leftMost(root.right,target);
        //if it's on right node's left most path
        if (onRight) {
            swap(root.left, root.right);
        }
        //is target on leftMost path rooted at root?
        return onLeft || onRight;
    }

Given a binary tree and two nodes, return the path between two nodes.

Solution 1 : Traverse twice (root, r1, r2)

• Step 1: find path from root to r1, r2
• Step 2: merge two linkedlist

  my solution: bottom up