pathSum 1

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.

Note: A leaf is a node with no children.

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

// comment:
// subtract/deduct each node.val from the target sum,
// UNTIL: if (root.left == null && root.right == null && sum - root.val == 0) return true;
//OTHERWISE: keep recursion and go deeper: return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);



        // First tentative idea: 
        // first sum all path, and store in an array  
        // then check their sum
        
    }
}

pathSum 2

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.
List<List<Integer>> resultList
这道二叉树路径之和在之前的基础上又需要找出路径 (可以参见我之前的博客 http://www.cnblogs.com/grandyang/p/4036961.html)，但是基本思想都一样，还是需要用深度优先搜索DFS，只不过数据结构相对复杂一点，需要用到二维的vector，而且每当DFS搜索到新节点时，都要保存该节点。而且每当找出一条路径之后，都将这个保存为一维vector的路径保存到最终结果二位vector中。List<List<Integer>> resultList
并且，每当DFS搜索到子节点，发现不是路径和时，返回上一个结点时，需要把该节点从一维vector中移除。(转载出处)

class Solution {
    private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    // A list of List<Integer>
    // List<List<Integer>> resultList
    public void pathSumInner(TreeNode root, int sum, Stack<Integer>path){
        
        path.push(root.val);
        
        if(root.left == null && root.right == null) {
            if (sum == root.val) resultList.add(new ArrayList<Integer>(path));
            // 只有最终符合条件的才会加入resultList
        }
        if(root.left != null) {
            pathSumInner(root.left, sum - root.val, path);
        }
        if(root.right != null) {
            pathSumInner(root.right, sum - root.val, path);
        }
        path.pop(); // 不符合条件的node，pop出Stack<Integer>(path)
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {return resultList;}
        Stack<Integer> path = new Stack<Integer>();
        pathSumInner(root, sum, path);
        return resultList;
    }
    
}

pathSum 3

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.