1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
/*
* 113. Path Sum II
Total Accepted: 83983 Total Submissions: 293023 Difficulty: Medium
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]
]
Hide Company Tags Bloomberg
Hide Tags Tree Depth-first Search
Hide Similar Problems (E) Path Sum (E) Binary Tree Paths
*/
package tree;
import java.util.*;
public class PathSumThree {
public static void main(String[] args) {
TreeNode root = new TreeNode(5);
TreeNode left = new TreeNode(4);
TreeNode right = new TreeNode(8);
root.left = left;
root.right = right;
left.left = new TreeNode(11);
left.left.left = new TreeNode(7);
left.left.right = new TreeNode(2);
right.left = new TreeNode(13);
right.right = new TreeNode(9);
right.right.left = new TreeNode(6);
right.right.right = new TreeNode(1);
PathSumThree pts = new PathSumThree();
int sum = 22;
List<List<Integer>> paths = pts.pathSum(root, sum);
System.out.println(paths);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
// https://leetcode.com/discuss/16980/dfs-with-one-linkedlist-accepted-java-solution
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> cur = new ArrayList<Integer>();
/*
* using ArrayList allows O(1) access to the each node, that means
* removing the last element takes only O(1). If you use LinkedList,
* initially we have traverse the list to the last node then remove it,
* which takes O(n) time. I
*/
dfs(root, sum, result, cur);
return result;
}
public void dfs(TreeNode root, int sum, List<List<Integer>> result, List<Integer> path) {
if (root == null)
return;
path.add(new Integer(root.val));
if (root.left == null && root.right == null && root.val == sum) {
result.add(new ArrayList(path)); // [[5, 4, 11, 2]]
// result.add(path); // [[]]
/*
* when you use add function of List, it just add a copy of
* reference of the object into the List instead of a new copy of
* the object. So if you don't create a new copy, all the reference
* you add to your result refer to the same object.
*
*/
} else {
dfs(root.left, sum - root.val, result, path);
dfs(root.right, sum - root.val, result, path);
}
path.remove(path.size() - 1);
}
}
|