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

约 5 分钟
文章信息 14 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 美团 拼多多 百度 商汤 猿辅导
标签
深度优先搜索 树 二叉树 回溯 二叉树路径总和问题

题目描述

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

image-20261001230752559

image-20260928195140463

image-20260928195140464

题意分析

返回所有从根节点出发、到叶子节点结束，且节点值之和等于 target 的路径。每条答案按从根到叶的顺序保存节点值。

路径不能从中间节点开始，也不能在内部节点结束；叶子指左右孩子都不存在的节点。节点值可以为负数，因此路径和可能增大也可能减小，不能仅凭当前和超过目标就放弃搜索。空树没有符合条件的路径。

解法：DFS 回溯根到叶路径

核心思路

[!blue]

深度优先搜索每一条根到叶路径。进入节点之前，path 保存从根到父节点的值，remain 表示目标值减去这些祖先的和。将当前值加入路径并从 remain 扣除后，两份状态就都对应从根到当前节点的路径。

只有当前节点是叶子且 remain == 0，才找到完整答案。内部节点即使剩余值已经为零，也必须继续往下，因为题目要求走到叶子，而且后续节点可能有正有负。

左右分支共享同一个路径容器。处理完当前节点的所有后代后，必须移除路径末尾的当前值，让父节点拿回进入这次调用之前的路径；这样下一条分支才能复用正确的公共前缀。每次加入与退出时删除一一对应，就是回溯需要恢复的状态。

remain 是整数，递归调用会得到自己的值副本，因此孩子对它的扣减不会污染兄弟分支，无需额外恢复。相反，收集答案时必须复制 path 的内容，否则后续删除或覆盖会改写已经保存的路径。

解题步骤

  1. 从根节点调用 DFS，初始路径为空，剩余目标为 target；遇到空节点直接返回。
  2. 将当前节点值加入 path，并执行 remain -= node.val。
  3. 若当前节点是叶子，在 remain == 0 时复制整条路径加入答案。
  4. 若不是叶子，递归搜索左右孩子，把当前剩余目标传下去。
  5. 两个分支处理完后删除路径末尾元素，再返回父调用。

代码实现

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)$。

关键点总结

[!green]

  • 叶子条件与目标和条件必须同时成立，才是一条有效的完整路径。
  • 递归入口的路径与剩余目标描述同一段祖先路径，加入当前值后同步更新。
  • 共享路径通过追加、删除恢复；整数参数按值传递，自然隔离各分支。
  • 路径副本只在命中时创建，避免每下降一层都复制整个前缀。

易错点总结

[!yellow]

  • 判断叶子要用左右孩子都为空，不能用任意一个为空；只有一个孩子的节点仍是内部节点。
  • 不能在内部节点剩余值为零时收集或停止，必须检查到叶子才算完成。
  • Java 的 ans.add(path) 只保存同一列表的引用，应创建新列表；Go 直接保存 slice 也可能共享底层数组，需要复制元素。
  • 命中后提前返回若跳过末尾删除，会让当前节点残留在共享路径中，污染之后的分支。
  • 负数可能使剩余目标重新增大，不能使用 remain < 0 作为剪枝条件。

相似题目

题目 难度 关联与区别
112. 路径总和 简单 匹配条件相同，原题只返回布尔值，本题需要维护路径并在命中时复制。
437. 路径总和 III 中等 原题统计任意起点的向下路径，本题只收集根到叶的完整路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/31743601
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！