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