这道题目主要是使用 回溯法+先序遍历。
以这题来记录一下回溯法的模板吧。
思路
先序遍历（递归模板）：
按照 “根、左、右” 的顺序，遍历树的所有节点。
路径记录：
在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表
回溯法体现：
每次左子树遍历到叶子结点后，下一次的回溯之前删除path中的尾结点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
|