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]
]
与112题方法类似 http://www.jianshu.com/p/faf516d9914d
Solution1:pre-order DFS(backtracking)
思路: 递归pre-order dfs来downwards累积cur_path (backtracking remove回溯)
Time Complexity: O(N) Space Complexity: O(N) 递归缓存
Solution2:Interative stack 法二, 纪录sum和cur_path 并 step back
则不用存sum进stack
Time Complexity: O(N) Space Complexity: O(N)
Solution3:backtracking 套路解法 Round1
Solution1 Code:
class Solution1 {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
List<Integer> cur_result = new LinkedList<Integer>();
dfs_path(result, cur_result, root, sum);
return result;
}
private void dfs_path(List<List<Integer>> result, List<Integer> cur_result, TreeNode root, int sum) {
if(root == null) return;
cur_result.add(new Integer(root.val));
if(root.left == null && root.right == null && sum == root.val) {
result.add(new LinkedList(cur_result));
cur_result.remove(cur_result.size() - 1); //remove last one for steping back (backtracking)
return;
}
dfs_path(result, cur_result, root.left, sum - root.val);
dfs_path(result, cur_result, root.right, sum - root.val);
cur_result.remove(cur_result.size() - 1);
}
}
Solution2 Code:
class Solution2 {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cur_path = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null) {
while(cur != null) {
stack.push(cur);
// process
cur_path.add(cur.val);
sum -= cur.val;
if(cur.left == null && cur.right == null && sum == 0) {
result.add(new ArrayList<Integer>(cur_path));
}
cur = cur.left;
}
// pop and sum_step_back togeter, but
// only do that after finishing processing its right_siblings,
// otherwise when visiting right_siblings, its root will be wrongly sum_step_back.
while (!stack.isEmpty() && stack.peek().right == cur) {
cur = stack.pop();
sum += cur.val; // sum: step back
cur_path.remove(cur_path.size() - 1);
}
cur = stack.isEmpty() ? null : stack.peek().right;
}
return result;
}
}
Solution3 Round1 Code:
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(root == null) return result;
List<Integer> cur_result = new LinkedList<Integer>();
cur_result.add(root.val);
dfs_path(result, cur_result, root, sum - root.val);
return result;
}
private void dfs_path(List<List<Integer>> result, List<Integer> cur_result, TreeNode root, int remain) {
if(root == null) return;
if(root.left == null && root.right == null && remain == 0) {
result.add(new LinkedList(cur_result));
return;
}
if(root.left != null) {
cur_result.add(root.left.val);
dfs_path(result, cur_result, root.left, remain - root.left.val);
cur_result.remove(cur_result.size() - 1); // steping back
}
if(root.right != null) {
cur_result.add(root.right.val);
dfs_path(result, cur_result, root.right, remain - root.right.val);
cur_result.remove(cur_result.size() - 1); // steping back
}
}
}
Solution3 Round2 Code:
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cur_res = new ArrayList<>();
if(root == null) return result;
dfsCheck(root, sum, cur_res, result);
return result;
}
private void dfsCheck(TreeNode root, int sum_left, List<Integer> cur_res, List<List<Integer>> result) {
if(root == null) return;
if(root.left == null && root.right == null && root.val == sum_left) {
cur_res.add(root.val);
result.add(new ArrayList<>(cur_res));
cur_res.remove(cur_res.size() - 1);
return;
}
cur_res.add(root.val);
dfsCheck(root.left, sum_left - root.val, cur_res, result);
dfsCheck(root.right, sum_left - root.val, cur_res, result);
cur_res.remove(cur_res.size() - 1);
}
}