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 andsum = 22,

              5             / /            4   8           /   / /          11  13  4         /  /      /        7    2      1

return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.

這道題挺簡單的，直接用recursive做就可以了。因為反正每一個node檢查的方式都一樣。

只要目前的sum減去正在檢查的node的value之后等于0，就可以return true。

所以程序還是很簡單的。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public boolean haspathSum(TreeNode root, int sum) {        if(root==null){            return false;        }        sum=sum-root.val;        if(root.left==null&&root.right==null){            if(sum==0){                return true;            }            return false;        }        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);    }}