二叉树中和为某一值的路径

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树,以及目标和 sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2   5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

提示:

  1. 节点总数 <= 10000

实际上就是先序遍历,记录路径,回退的时候记得remove掉叶子


解法1 :7ms

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
class Solution {
List<List<Integer>> result = new ArrayList<>();
int sum;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
this.sum = sum;
lookSum(root, new ArrayList<>());
return result;
}

public void lookSum(TreeNode root,List<Integer> integerList){
if(root == null){
return;
}
//因为Java是传递的引用,我们不能共同用一个list。而是每次new一个,复用之前的路径
ArrayList<Integer> integerArrayList = new ArrayList<>(integerList);
integerArrayList.add(root.val);
if(root.left == null && root.right == null){
if (integerArrayList.stream().mapToInt(Integer::intValue).sum() == sum) {
result.add(integerArrayList);
}
return;
}
lookSum(root.left, integerArrayList);
lookSum(root.right, integerArrayList);
}
}

执行用时:7 ms
内存消耗:42.2 MB

缺点:

  • 每次都new了
  • 每次都计算了数组了和了
  • stream 是要慢一点

优化 :3ms

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
class Solution {
List<List<Integer>> result = new ArrayList<>();
int sum;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
this.sum = sum;
lookSum(root, new ArrayList<>(),0);
return result;
}

public void lookSum(TreeNode root,List<Integer> integerList,int cur_sum){
if(root == null){
return;
}
ArrayList<Integer> integerArrayList = new ArrayList<>(integerList);
integerArrayList.add(root.val);
if(root.left == null && root.right == null){
if (cur_sum+root.val == sum) {
result.add(integerArrayList);
}
return;
}
lookSum(root.left, integerArrayList,cur_sum+root.val);
lookSum(root.right, integerArrayList, cur_sum + root.val);
}
}

执行用时:3 ms
内存消耗:42.9 MB
缺点

  • 不用每次都计算和了,把和标记下
  • 每次都new有点不划算

优化 :1ms

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
class Solution {
List<List<Integer>> result = new ArrayList<>();
int sum;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
this.sum = sum;
lookSum(root, new ArrayList<>(),0);
return result;
}

public void lookSum(TreeNode root,List<Integer> integerList,int cur_sum){
if(root == null){
return;
}
integerList.add(root.val);
if(root.left == null && root.right == null){
if (cur_sum+root.val == sum) {
result.add(new ArrayList<>(integerList));
}
//回退记得remove
integerList.remove(integerList.size() - 1);
return;
}
lookSum(root.left, integerList,cur_sum+root.val);
lookSum(root.right, integerList, cur_sum + root.val);
//回退记得remove
integerList.remove(integerList.size() - 1);
}
}

执行用时:1 ms
内存消耗:39.7 MB