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