路径和-给定二叉树和求和，确定树是否具有根到叶路径

Question

给定二叉树和求和，确定树是否具有根到叶路径，使得沿路径的所有值相加等于给定的总和。

Answer 1

思路一：递归\n这道题用递归来解的话非常简单，我们把二叉树的根节点记为 root，如果我们想判断一颗二叉树是否存在路径和 sum，那么只需判断其左子树或者右子树是否存在路径和 sum-root.val。
代码如下：

public boolean hasPathSum(TreeNode root, int sum)
 {    if (root == null)     return false;    int val = root.val;   
 if (root.left == null && root.right == null && val == sum)      
 return true;   
 return hasPathSum(root.left, sum - val) || hasPathSum(root.right, sum - val);}

思路二：迭代——用栈代替递归利用栈先入后出的特点，我们可以对思路一中的递归代码进行改造，代码如下：

public boolean hasPathSum_iteration(TreeNode root, int sum){
    if (root == null)
        return false;
    Stack<TreeNode> stack = new Stack<>();
    Stack<Integer> path = new Stack<>();

    TreeNode t = root;
    Integer val = root.val;
    stack.push(t);
    path.push(val);
    while (!stack.isEmpty()){
        t = stack.pop();
        val = path.pop();
        if (t.left == null && t.right == null && sum == val){ //到达了叶子结点，且路径总和正好等于sum
            return true;
        }
        if (t.left != null){
            stack.push(t.left);
            path.push(val + t.left.val);
        }
        if (t.right != null){
            stack.push(t.right);
            path.push(val + t.right.val);
        }
    }
    return false;
}