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 Sum1没什么很大的区别，只是要记录结果就行。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList> res = new ArrayList<ArrayList>();
        if (root == null)
        {
            return res;
        }
        if (root.left == null && root.right == null)
        {
            if (sum == root.val) // found one
            {
                ArrayList temp = new ArrayList();
                temp.add(root.val);
                res.add(temp);
            }
            return res;
        }
        int nextSum = sum - root.val;
        ArrayList<ArrayList> lList = pathSum(root.left, nextSum);
        ArrayList<ArrayList> rList = pathSum(root.right, nextSum);
        if (!lList.isEmpty())
        {
            for(ArrayList l : lList)
            {
                l.add(0, root.val);
                res.add(l);
            }
        }
        if (!rList.isEmpty())
        {
            for(ArrayList l : rList)
            {
                l.add(0, root.val);
                res.add(l);
            }
        }
        return res;
    }
}

Second Submission:

Same idea as Path Sum, just record the result when hit a leaf and leaf sum is the same as leaf value

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        findPath(sum, root, new ArrayList<Integer>());
        return result;
    }
    
    public void findPath(int sum, TreeNode root, ArrayList<Integer> last) {
        if (root == null)
            return;
        ArrayList<Integer> temp = new ArrayList<Integer>(last);
        temp.add(root.val);
        if (root.left == null && root.right == null) {
            if (root.val == sum) {
                result.add(temp);
                return;
            }
            else
                return;
        }
        if (root.left != null) {
            findPath(sum - root.val, root.left, temp); 
        }
        if (root.right != null) {
            findPath(sum - root.val, root.right, temp);
        }
    }
}

Advertisements