112. Path Sum.md

#112. Path Sum

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.

思路：使用递归，到叶子节点再判断是否该路径的和为sum，若是直接返回结果，并不做其他判断。

Java Solution(1)

public class Solution {
    boolean has = false;
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        return findRootToLeaf(root,0,sum);
    }
    public  boolean findRootToLeaf(TreeNode node,int pre,int sum){
        boolean find = false;
        if(node.left==null&&node.right==null) {
            if(pre+node.val==sum){
                has = true;
                find = true;
            }
        }
            pre += node.val;
            if(!has&&node.left!=null)
                find = findRootToLeaf(node.left,pre,sum);
            if(!has&&node.right!=null)
                find = findRootToLeaf(node.right,pre,sum);
        return find;
    }
}

Java Solution(2)

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        return findRootToLeaf(root,0,sum);
    }
    public  boolean findRootToLeaf(TreeNode node,int pre,int sum){
        if(node==null) return false;
        if(node.left==null&&node.right==null)
            if(pre+node.val==sum)
                return true;
            else
                return false;
       pre += node.val;
       return findRootToLeaf(node.left,pre,sum) || findRootToLeaf(node.right,pre,sum);
    }
}

经过两次简化之后得到的最简结果咯。

Java Solution(3)

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

Java Solution(Iterative)

public boolean hasPathSum(TreeNode root, int result){
    if(root == null)
        return false;
    ArrayList<Integer> list = new ArrayList<Integer>();
    ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
    ArrayDeque<Integer> sums = new ArrayDeque<Integer>();
    stack.push(root);
    sums.push(0);
    while(!stack.isEmpty()){
        TreeNode cur = stack.pop();
        int sum = sums.pop() + cur.val;
        if(cur.left == null && cur.right == null){
            if(sum == result)
                return true;
        }
        if(cur.left != null){
            stack.push(cur.left);
            sums.push(sum);
        }
        if(cur.right != null){
            stack.push(cur.right);
            sums.push(sum);
        }
    }
    return false;
}