LeetCode 剑指 Offer 34. 二叉树中和为某一值的路径

2025-08-27 HGNULB 约 7 分钟

文章信息 14 个分类 5 个标签

分类

LeetCode CodeTop 中等未解决 20-50 字节跳动美团腾讯猿辅导百度拼多多商汤剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 34. 二叉树中和为某一值的路径

题意分析

给定一棵二叉树和一个目标值，要找出所有从根节点出发、到叶子节点结束、且沿途节点值之和恰好等于目标值的路径，并把每条路径按从根到叶的顺序以节点值列表的形式返回。

「根到叶」这个限定是全题最硬的约束，两端都不能松动。起点必须是根，不能从中间某个节点开始；终点必须是叶子，即左右孩子同时为空的节点，哪怕走到某个内部节点时累计和就已经等于目标值，也不能就地收工。这与 437 那种「任意节点到任意节点」的路径题是完全不同的两道题。

交付的是路径列表而不是数量，这决定了两件事：一是不能只维护一个和，还必须把沿途走过的节点值序列真实地记下来；二是同一时刻只存在一条「当前路径」，而答案里要放进去多条，因此存进答案的那一份和正在被修改的那一份必须彻底脱钩。

约束里还有一个容易被忽略的信号：节点值可以是负数。这意味着累计和沿着一条路径走下去并不是单调递增的，任何形如「剩余目标已经小于 0 就提前返回」的剪枝都是错的。另外答案对路径之间的顺序没有要求。

边界情形：空树直接返回空列表；根节点本身就是叶子且值等于目标时，答案是只含一个元素的单条路径；同一棵树里可能有多条路径都满足条件，也可能一条都没有，此时返回空列表而不是 null。

解法：DFS 回溯根到叶路径

核心思路

DFS 的递归栈天然对应一条从根到当前节点的路径。用可变列表 path 记录这条路径：进入节点时追加，离开节点时删除；用 remain 记录扣除当前路径后还差多少。这样兄弟分支可以复用公共前缀，无需为每个节点重新构造路径。

递归不变量是：进入 dfs(node, remain) 时，path 保存从根到 node 父节点的路径，remain 是目标值减去该路径之和；加入 node.val 后，两者就对应根到当前节点。只有当前节点是叶子且新的 remain == 0，才得到合法答案。

函数返回前必须弹出当前节点，使 path 恢复到调用前的状态。命中时还要复制 path：答案需要保存这一刻的路径内容，而后续回溯会继续修改原列表。由上述不变量可知，DFS 会检查每一条根到叶路径且只收集和为目标值的路径，因此既不漏解也不误收内部节点。

解题步骤

从根开始 DFS，维护当前路径 path 和剩余目标 remain；空节点直接返回。

进入节点时把节点值加入 path，并从 remain 中减去该值。

若当前节点是叶子且 remain == 0，把 path 的副本加入结果集。

若不是叶子，继续搜索左右子树；节点值允许为负数，不能根据 remain 的正负提前剪枝。

离开节点前删除 path 末尾元素，恢复现场后再返回父节点。

例如目标值为 22 时，路径 [5,4,11,2] 到达叶子后剩余值恰好为 0，复制进答案；回溯到根后再搜索右子树，还能得到 [5,8,4,5]，两条路径互不污染。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, target, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(TreeNode node, int remain,
                     List<Integer> path, List<List<Integer>> ans) {
        if (node == null) {
            return;
        }

        path.add(node.val);
        remain -= node.val;
        if (node.left == null && node.right == null) {
            if (remain == 0) {
                ans.add(new ArrayList<>(path));
            }
        } else {
            dfs(node.left, remain, path, ans);
            dfs(node.right, remain, path, ans);
        }
        path.remove(path.size() - 1);
    }
}

func pathSum(root *TreeNode, target int) [][]int {
    ans := make([][]int, 0)
    path := make([]int, 0)

    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, remain int) {
        if node == nil {
            return
        }

        path = append(path, node.Val)
        remain -= node.Val
        if node.Left == nil && node.Right == nil {
            if remain == 0 {
                copied := append([]int(nil), path...)
                ans = append(ans, copied)
            }
        } else {
            dfs(node.Left, remain)
            dfs(node.Right, remain)
        }
        path = path[:len(path)-1]
    }

    dfs(root, target)
    return ans
}

复杂度分析

时间复杂度：$O(n+L)$，其中 $n$ 是节点数，$L$ 是所有答案路径的节点总数。遍历每个节点一次，命中时还需复制路径；最坏情况下 $L$ 可达 $O(n^2)$。

空间复杂度：不计返回结果为 $O(h)$，其中 $h$ 是树高，来自递归栈和当前路径；结果本身占 $O(L)$。

关键点总结

路径必须从根到叶：累计和在内部节点达到目标也不能收集。

path 的追加与删除必须成对，保证每个子树开始时都拿到正确的公共前缀。

收集答案时复制路径；Java 列表和 Go slice 都是共享可变存储，直接保存会被后续回溯改写。

数值状态适合按值传参，路径状态适合共享一份并回溯，既清晰又避免反复复制。

面试时要主动说明节点可能为负，因此不存在“剩余值小于 0 就停止”的单调性剪枝。

易错点总结

叶子必须满足 left == null && right == null。若写成逻辑或，只有一个孩子的内部节点也会被误判。

不能在非叶子节点因累计和等于目标就收集。例如 [1,2]、目标 1 的正确答案是空列表。

Java 中 ans.add(path) 只保存同一个列表引用；遍历结束后答案可能全为空，必须使用 new ArrayList<>(path)。

Go 中 append(ans, path) 仍可能共享底层数组，必须先用 append([]int(nil), path...) 复制。

命中后若提前 return，会跳过末尾的回溯操作并污染兄弟路径；应让所有分支都经过统一的弹出逻辑。

不能用 remain < 0 剪枝。例如路径 [5,-2]、目标 3 会先出现负的剩余值，随后才回到 0。

相似题目

题目	难度	考察点
112. 路径总和	简单	只问存在性，无需维护路径列表，找到一条即可短路返回
113. 路径总和 II	中等	与本题完全同题，可直接互抄，是拷贝快照这一考点的标准出处
437. 路径总和 III	中等	起止点任意，改用前缀和加哈希表统计，回溯时要撤销的是哈希计数
129. 求根节点到叶节点数字之和	中等	沿途状态是十进制拼数 `cur * 10 + val`，只需累加结果无需保存路径
257. 二叉树的所有路径	简单	收集全部根到叶路径且不带和的约束，输出是字符串而非列表
404. 左叶子之和	简单	需要在父节点侧判断孩子是否为左叶子，判定点不在当前节点上
1022. 从根到叶的二进制数之和	简单	与 129 同构但进制为二，状态更新写成 `cur * 2 + val`
LCR 049. 求根节点到叶节点数字之和	中等	与 129 同题，可对比递归传参与显式栈两种写法