112. Path Sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 

The basic idea is to subtract the value of current node from sum
until it reaches a leaf node and the subtraction equals 0, then we know that we got a hit.
Otherwise the subtraction at the end could not be 0.

回忆一下recursion的写法:

Recursion

a) 表象上：function call itself
b) 实质上：Boil a big problem to smaller size(size n depends on size n-1, n-2,…. or n/2)

c) Implementation:
1.Basis case: Smallest problem to solve.
2.Recursion Rule: how to make the problem smaller.

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {return false;}
        if (root.left == null && root.right == null && sum - root.val == 0){
            return true;    // Base case: reach the leave 
        // Or you can: if(root.left == null && root.right == null) return sum == root.val;
        // This means: when you reach the leaf node, its children is null AND itself consist of the last element added to SUM.
         // Notice that: the SUM is the rest SUM' - the residual value to original SUM.
        }
        return hasPathSum(root.right, sum - root.val) || hasPathSum(root.left, sum - root.val);     
        // boil into smaller size: go into the left/right child and check them
    }
}

437. Path Sum III

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

(同时也注意到将binary tree 转化为array，
是一层层往下排列的)

从Leaf node开始向上，到达一个node:
sum == target;
num_path++;

可能情况：
logn层时，n leaf nodes；
n层时，1 leaf nodes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// class Solution {
//     public int pathSum(TreeNode root, int sum) {
//         if (root == null) { return null;}
//         for (int i = 0; i < root.length; i++ ) {
//             // How choose one node i as the sub-root 
            
//         }
        
//     }
// }

// How to choose one node i as the sub-root 
// You can do it recursively, // dynamic programming

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) { return 0;}
            // How choose one node i as the sub-root?
            // maybe the only way is to use recursion / dynamic programming
        return asRootPathsBelow(root, sum) + pathSum(root.left, sum) 
            + pathSum(root.right, sum); // TAKE CARE of this line!
        }
        


// def another function: asRootPathsBelow
// count the number of paths which satisfy the sum requirement
//
    private int asRootPathsBelow(TreeNode node, int sum) {
        if (node == null) { return 0;}
        return ( node.val == sum ? 1 : 0 ) 
            + asRootPathsBelow(node.left, sum - node.val) 
            + asRootPathsBelow(node.right, sum - node.val);
    }


}