树回溯
# 257. 二叉树的所有路径 (opens new window)
class Solution {
List<String> ret = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root,new StringBuilder());
return ret;
}
void dfs(TreeNode node,StringBuilder path){
if(node.left==null && node.right==null){
ret.add(path.toString()+node.val);
return ;
}
// 想想这个为什么放在判断语句下面？
int start = path.length();
path.append(node.val).append("->");
if(node.left!=null)
dfs(node.left,path);
if(node.right!=null)
dfs(node.right,path);
path.delete(start,path.length());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 112. 路径总和 (opens new window)
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
return dfs(root,targetSum);
}
boolean dfs(TreeNode root,int targetSum){
if(root.left==null && root.right==null &&
targetSum-root.val==0){
return true;
}
// 选左边
if(root.left!=null){
if(dfs(root.left,targetSum-root.val)){
return true;
}
}
// 选右边
if(root.right!=null){
if(dfs(root.right,targetSum-root.val)){
return true;
}
}
return false;
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 113. 路径总和 II (opens new window)
class Solution {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root==null) return ret;
dfs(root,targetSum);
return ret;
}
void dfs(TreeNode root,int targetSum){
path.add(root.val);
if(root.left==null && root.right==null &&
targetSum-root.val==0){
ret.add(new ArrayList<>(path));
return ;
}
if(root.left!=null){
dfs(root.left,targetSum-root.val);
path.remove(path.size()-1);
}
if(root.right!=null){
dfs(root.right,targetSum-root.val);
path.remove(path.size()-1);
}
return ;
}
}
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
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
# 129. 求根节点到叶节点数字之和 (opens new window)
class Solution {
StringBuilder path = new StringBuilder();
int ret;
public int sumNumbers(TreeNode root) {
dfs(root);
return ret;
}
void dfs(TreeNode root){
if(root==null) return ;
path.append(root.val);
if(root.left==null && root.right==null){
ret += Integer.parseInt(path.toString());
}
if(root.left!=null){
dfs(root.left);
path.deleteCharAt(path.length()-1);
}
if(root.right!=null){
dfs(root.right);
path.deleteCharAt(path.length()-1);
}
return ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 437. 路径总和 III (opens new window)
class Solution {
int ret = 0;
public int pathSum(TreeNode root, int targetSum) {
if(root==null)
return 0;
dfs(root,targetSum);
pathSum(root.left,targetSum);
pathSum(root.right,targetSum);
return ret;
}
void dfs(TreeNode node,int targetSum){
if(node==null)
return ;
// 简单可以这么写，但是其它地方都不要再-node.val了；
//targetSum -= node.val;
if(targetSum-node.val==0)
ret++;
if(node.left!=null)
dfs(node.left,targetSum-node.val);
if(node.right!=null)
dfs(node.right,targetSum-node.val);
// 简单写这句不用加，压根不会执行这句话
//target += node.val
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25