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.
最先想到的就是使用递归了，我的方法使用了一个全局变量来记录整棵树中是否存在这样一个路径等于给出的数字。但是这个算法无论如何都会遍历整个二叉树，其实我们只要找到一条路符合要求就可以退出了。

var hasPathSum = function(root, sum) {
    //递归1
    if (!root) {
        return false;
    }
    var result = false;
    var help = function(root,sumRecord) {
        var sumNow = sumRecord+root.val;
        if (root.right) 
            help(root.right,sumNow);
        if (root.left) 
            help(root.left,sumNow);
        if (!root.left&&!root.right) {
            if (sumNow===sum)
                result = result || true;
            else 
                result = result || false;
        }
    };
    help(root,0);
    return result;
}

第二个递归算法比较简洁，直接利用给出的sum，在叶子节点减到0就意味着符合要求。这里就不用使用help函数了，直接递归就好，比较简洁，但是其实还是遍历了整棵树，本质上没有区别。

var hasPathSum = function(root, sum) {
    if (root === null) return false;
    sum = sum - root.val;
    if (root.left === null && root.right === null && sum === 0) return true;
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
};

使用递归我想不到怎么可以不遍历整棵树，于是只好换一种思路，使用深度优先遍历来进行每次从栈顶取出一个节点的时候，就将这个节点的值加到它的左右子节点中，并把左右节点入栈，如果没有子节点，就将当前节点的值与要求的总和做对比，符合就直接返回true。

var hasPathSum = function(root, sum) {
    if (!root) {
        return false;
    }
    var stack = [root];
    while (stack.length!==0) {
        var node = stack.pop();
        if (node.left) {
            node.left.val += node.val;
            stack.push(node.left);
        }
        if (node.right) {
            node.right.val += node.val;
            stack.push(node.right);
        }
        if (!node.left&&!node.right) {
            if (node.val===sum)
                return true;
        }
    }
    return false;
};

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:Given the below binary tree and sum = 22,

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

return

[
   [5,4,11,2],
   [5,8,4,5]
]

这里其实和上面的思路一样，就是多一个path的记录

var pathSum = function(root, sum) {
    var res = [];
    var help = function(root,sumNow,path) {
        sumNow = sumNow + root.val;
        var pathNow = path.concat();
        pathNow.push(root.val);
        if (root.left)
            help(root.left, sumNow, pathNow);
        if (root.right)
            help(root.right, sumNow, pathNow);
        if (!root.left&&!root.right&&sumNow===sum) 
            res.push(pathNow);
    };
    if (root!==null)
        help(root,0,[]);
    return res;
};