forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Path Sum.java
More file actions
123 lines (103 loc) · 2.85 KB
/
Binary Tree Path Sum.java
File metadata and controls
123 lines (103 loc) · 2.85 KB
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
E
Binary Tree的一个基本题。
遍历到底，比较sum vs. target。
注意divide的情况。要把遍历的例子写写。
LeetCode: Path Sum II
```
/*
Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.
A valid path is from root node to any of the leaf nodes.
Example
Given a binary tree, and target = 5:
1
/ \
2 4
/ \
2 3
return
[
[1, 2, 2],
[1, 4]
]
Tags Expand
Binary Tree Binary Tree Traversal
*/
/*
Thoughts:
path: has to be from root to leaf.
binary tree: no order logic in the tree.
DPS on all nodes. If final sum == target, add list of nodes into rst
*/
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
/*
3.1.2016 Recap
Same approach
*/
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
if (root == null) {
return rst;
}
dfs(rst, new ArrayList<Integer>(), root, 0, sum);
return rst;
}
public void dfs(List<List<Integer>> rst, ArrayList<Integer> list, TreeNode node, int add, int sum) {
list.add(node.val);
if (node.left == null && node.right == null) {
if (add + node.val == sum) {
rst.add(new ArrayList<Integer>(list));
}
return;
}
if (node.left != null) {
dfs(rst, list, node.left, add + node.val, sum);
list.remove(list.size() - 1);
}
if (node.right != null) {
dfs(rst, list, node.right, add + node.val, sum);
list.remove(list.size() - 1);
}
}
}
public class Solution {
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
if (root == null) {
return rst;
}
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(root.val);
traversal(rst, list, root, root.val, target);
return rst;
}
public void traversal(List<List<Integer>> rst, ArrayList<Integer> list, TreeNode node, int sum, int target) {
if (node.left == null && node.right == null) {
if (sum == target) {
rst.add(new ArrayList<Integer>(list));
}
return;
}
if (node.left != null) {
list.add(node.left.val);
traversal(rst, list, node.left, sum + node.left.val, target);
list.remove(list.size() - 1);
}
if (node.right != null) {
list.add(node.right.val);
traversal(rst, list, node.right, sum + node.right.val, target);
list.remove(list.size() - 1);
}
}
}
```