113. 路径总和 II
题目描述
输入二叉树的根节点 root 和一个整数 targetSum。
找出所有从根出发、到某个叶子节点结束，并且节点值之和等于 targetSum 的路径。叶子节点指没有孩子的节点。
每条路径写成从根到叶子依次经过的节点值列表。返回由这些路径组成的列表；一条都没有时返回 []。树用层序数组表示，null 代表空位。
示例 1
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
解释：5+4+11+2 与 5+8+4+5 都等于 22。
示例 2
输入：root = [1,2,3], targetSum = 5 输出：[]
解释：根到叶子的路径和只有 3 和 4。
示例 3
输入：root = [1,2], targetSum = 0 输出：[]
解释：唯一的根到叶子路径 1 -> 2 和为 3，不等于 0。
数据范围
- 节点总数在
[0, 5000]之间。 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题思路：回溯（深度优先搜索）
深度优先搜索加回溯。用一个 path 列表记录从根到当前节点的路径，进入节点时 append，离开时 pop。同时把剩余值 rest 往下传，到达叶子且 rest 为 0 时，把 path 的一份拷贝加入结果。
为什么正确
进入 dfs(node, rest) 时，path 恰好是根到 node 父节点的路径，rest 等于 targetSum 减去 path 中各值之和。
复杂度分析
时间 O(n^2)（最坏每个叶子都要拷贝长为 O(n) 的路径），空间 O(h) 不计结果。
易错点
加入结果时必须拷贝 path（path[:]），否则之后的 pop 会把结果里的列表一起改掉。离开节点前别忘了 path.pop()。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res, path = [], []
def dfs(node, rest):
if not node:
return
path.append(node.val)
rest -= node.val
if not node.left and not node.right and rest == 0:
res.append(path[:])
dfs(node.left, rest)
dfs(node.right, rest)
path.pop()
dfs(root, targetSum)
return resclass Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void dfs(TreeNode node, int rest) {
if (node == null) {
return;
}
path.add(node.val);
rest -= node.val;
if (node.left == null && node.right == null && rest == 0) {
res.add(new ArrayList<>(path));
}
dfs(node.left, rest);
dfs(node.right, rest);
path.remove(path.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root, targetSum);
return res;
}
}class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(TreeNode* node, int rest) {
if (!node) {
return;
}
path.push_back(node->val);
rest -= node->val;
if (!node->left && !node->right && rest == 0) {
res.push_back(path);
}
dfs(node->left, rest);
dfs(node->right, rest);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root, targetSum);
return res;
}
};func pathSum(root *TreeNode, targetSum int) [][]int {
res, path := [][]int{}, []int{}
var dfs func(node *TreeNode, rest int)
dfs = func(node *TreeNode, rest int) {
if node == nil {
return
}
path = append(path, node.Val)
rest -= node.Val
if node.Left == nil && node.Right == nil && rest == 0 {
res = append(res, append([]int{}, path...))
}
dfs(node.Left, rest)
dfs(node.Right, rest)
path = path[:len(path)-1]
}
dfs(root, targetSum)
return res
}var pathSum = function(root, targetSum) {
const res = [], path = [];
const dfs = (node, rest) => {
if (!node) {
return;
}
path.push(node.val);
rest -= node.val;
if (!node.left && !node.right && rest === 0) {
res.push([...path]);
}
dfs(node.left, rest);
dfs(node.right, rest);
path.pop();
};
dfs(root, targetSum);
return res;
};function pathSum(root: TreeNode | null, targetSum: number): number[][] {
const res: number[][] = [], path: number[] = [];
const dfs = (node: TreeNode | null, rest: number): void => {
if (!node) {
return;
}
path.push(node.val);
rest -= node.val;
if (!node.left && !node.right && rest === 0) {
res.push([...path]);
}
dfs(node.left, rest);
dfs(node.right, rest);
path.pop();
};
dfs(root, targetSum);
return res;
}其他解法
回溯用一条共享路径边走边恢复，最简洁；广度优先搜索只在命中时沿父指针还原路径，适合不想递归的场景。
解法 2：广度优先搜索 + 父指针 时间 O(n²)，空间 O(n)
队列里保存节点和到它为止的路径和，并用哈希表记录每个节点的父节点。遇到路径和等于 targetSum 的叶子时，沿父指针走回根得到路径，再反转加入结果。
没有递归，深链树不会栈溢出。要多存一张父节点表，代码比回溯长。
from collections import deque
class Solution:
def pathSum(self, root, targetSum):
res = []
if not root:
return res
parent = {root: None}
queue = deque([(root, root.val)])
while queue:
node, s = queue.popleft()
if not node.left and not node.right:
if s == targetSum:
path = []
cur = node
while cur:
path.append(cur.val)
cur = parent[cur]
res.append(path[::-1])
continue
for child in (node.left, node.right):
if child:
parent[child] = node
queue.append((child, s + child.val))
return resclass Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Map<TreeNode, TreeNode> parent = new HashMap<>();
parent.put(root, null);
Deque<TreeNode> nodes = new ArrayDeque<>();
Deque<Integer> sums = new ArrayDeque<>();
nodes.offer(root);
sums.offer(root.val);
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
int s = sums.poll();
if (node.left == null && node.right == null) {
if (s == targetSum) {
List<Integer> path = new ArrayList<>();
for (TreeNode cur = node; cur != null; cur = parent.get(cur)) path.add(cur.val);
Collections.reverse(path);
res.add(path);
}
continue;
}
for (TreeNode child : new TreeNode[]{node.left, node.right}) {
if (child != null) {
parent.put(child, node);
nodes.offer(child);
sums.offer(s + child.val);
}
}
}
return res;
}
}class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res;
if (!root) return res;
unordered_map<TreeNode*, TreeNode*> parent;
parent[root] = nullptr;
queue<pair<TreeNode*, int>> q;
q.push({root, root->val});
while (!q.empty()) {
auto [node, s] = q.front(); q.pop();
if (!node->left && !node->right) {
if (s == targetSum) {
vector<int> path;
for (TreeNode* cur = node; cur; cur = parent[cur]) path.push_back(cur->val);
reverse(path.begin(), path.end());
res.push_back(path);
}
continue;
}
for (TreeNode* child : {node->left, node->right}) {
if (child) {
parent[child] = node;
q.push({child, s + child->val});
}
}
}
return res;
}
};func pathSum(root *TreeNode, targetSum int) [][]int {
res := [][]int{}
if root == nil {
return res
}
type item struct {
node *TreeNode
sum int
}
parent := map[*TreeNode]*TreeNode{root: nil}
queue := []item{{root, root.Val}}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
node, s := cur.node, cur.sum
if node.Left == nil && node.Right == nil {
if s == targetSum {
path := []int{}
for p := node; p != nil; p = parent[p] {
path = append(path, p.Val)
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
res = append(res, path)
}
continue
}
for _, child := range []*TreeNode{node.Left, node.Right} {
if child != nil {
parent[child] = node
queue = append(queue, item{child, s + child.Val})
}
}
}
return res
}var pathSum = function(root, targetSum) {
const res = [];
if (!root) return res;
const parent = new Map([[root, null]]);
const queue = [[root, root.val]];
for (let i = 0; i < queue.length; i++) {
const [node, s] = queue[i];
if (!node.left && !node.right) {
if (s === targetSum) {
const path = [];
for (let cur = node; cur; cur = parent.get(cur)) path.push(cur.val);
res.push(path.reverse());
}
continue;
}
for (const child of [node.left, node.right]) {
if (child) {
parent.set(child, node);
queue.push([child, s + child.val]);
}
}
}
return res;
};function pathSum(root: TreeNode | null, targetSum: number): number[][] {
const res: number[][] = [];
if (!root) return res;
const parent = new Map<TreeNode, TreeNode | null>([[root, null]]);
const queue: [TreeNode, number][] = [[root, root.val]];
for (let i = 0; i < queue.length; i++) {
const [node, s] = queue[i];
if (!node.left && !node.right) {
if (s === targetSum) {
const path: number[] = [];
for (let cur: TreeNode | null = node; cur; cur = parent.get(cur)!) path.push(cur.val);
res.push(path.reverse());
}
continue;
}
for (const child of [node.left, node.right]) {
if (child) {
parent.set(child, node);
queue.push([child, s + child.val]);
}
}
}
return res;
}