Time = O(n): 遍历树中的每一个节点一次
Space = O(n)
注意：不能直接用 if (root.val == sum) 写，一个edge case是[1,2], 1，要用 if (root.left == null && root.right == null) 判断是否到了根部。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) { // whether root is null
return false;
}
if (root.left == null && root.right == null) { // whether root is leaf node
return root.val == sum;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}