https://leetcode.com/problems/path-sum/description/<br />Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.<br /><br />For example:<br />Given the below binary tree and sum = 22,<br /><br /><br /> / \<br /> 4 8<br /> / / \<br /> 11 13 4<br /> / \ \<br /> 7 2 1<br />return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.<br /><br />注意题意: if the tree has a root-to-leaf path 这道题是要走到底，不是走一半！!<br />如果走一半停止，那会很复杂<br /><br />这道题可以用pre-order对于二叉树自上到下来递归，每次递归生成一个减掉root.val的新sum，<br />然后先判断sum是否为零并且当前的root是否为leaf，若满足则return true，否则对其左儿子和右儿子分别递归，返回左儿子结果||右儿子结果，<br />如此往复直到root是null（本身是leaf，此时返回false）。<br /><br />time: o(n) space:o(n)<br /><br /><br /><br />
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false ;
int newSum = sum - root.val ;
//判断sum是否为零并且当前的root 是否没有叶子了（已经走到底，不用再走了）： 这道题是要走到底，不是走一半！
if (root.left == null && root.right == null && newSum ==0){
return true ;
}
boolean leftRes = hasPathSum(root.left, newSum) ; //细节， 跟节点的 newSum 并不会被一边所改变
boolean rightRes = hasPathSum(root.right,newSum) ;
//如果左边或者右边有一边走到底并且走通了，则这一层返回 TRUE， 一直层层返回到最顶层 TRUE
return leftRes || rightRes;
} 