LC.112.Path Sum

https://leetcode.com/problems/path-sum/description/
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.

For example:
Given the below binary tree and sum = 22,

              5
             / 
            4   8
           /   / 
          11  13  4
         /        
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

注意题意: if the tree has a root-to-leaf path 这道题是要走到底，不是走一半！!
如果走一半停止，那会很复杂

这道题可以用pre-order对于二叉树自上到下来递归，每次递归生成一个减掉root.val的新sum，
然后先判断sum是否为零并且当前的root是否为leaf，若满足则return true，否则对其左儿子和右儿子分别递归，返回左儿子结果||右儿子结果，
如此往复直到root是null（本身是leaf，此时返回false）。

time: o(n) space:o(n)

 1 public boolean hasPathSum(TreeNode root, int sum) {
 2         if (root == null) return false ;
 3         int newSum = sum - root.val ;
 4         //判断sum是否为零并且当前的root 是否没有叶子了（已经走到底，不用再走了）： 这道题是要走到底，不是走一半！
 5         if (root.left == null && root.right == null && newSum ==0){
 6             return true ;
 7         }
 8         boolean leftRes = hasPathSum(root.left, newSum) ; //细节， 跟节点的 newSum 并不会被一边所改变
 9         boolean rightRes = hasPathSum(root.right,newSum) ;
10         //如果左边或者右边有一边走到底并且走通了，则这一层返回 TRUE， 一直层层返回到最顶层 TRUE
11         return leftRes || rightRes;
12     }

网上还有一种做法用STACK 现在无法理解，以后再弄！