问答题【1002/1911】 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 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]]

示例 2：

预览

输入： root = [1,2,3], targetSum = 5 输出： []

示例 3：

输入： root = [1,2], targetSum = 0 输出： []

提示：

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val, left, right) {
4 *     this.val = (val===undefined ? 0 : val)
5 *     this.left = (left===undefined ? null : left)
6 *     this.right = (right===undefined ? null : right)
7 * }
8 */
9/**
10 * @param {TreeNode} root
11 * @param {number} target
12 * @return {number[][]}
13 */
14var pathSum = function(root, target) {
15
16};
难度：
2022-05-16 创建

参考答案：

解题思路

深度优先遍历

  • 每层都三个参数，一个是当前结点，一个是 target 剩余值，一个是总路径数组
  • 当往二叉树深处进行遍历时，如果 target 剩余值跟结点值相等且左右子树为空(叶子结点)，则满足要求，往 result 压入当前总路径数组 path
  • 对于左右子树不为空的结点，继续往左或右子树进行遍历，直到叶子结点
1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val, left, right) {
4 *     this.val = (val===undefined ? 0 : val)
5 *     this.left = (left===undefined ? null : left)
6 *     this.right = (right===undefined ? null : right)
7 * }
8 */
9/**
10 * @param {TreeNode} root
11 * @param {number} target
12 * @return {number[][]}
13 */
14
15var pathSum = function (root, sum) {
16    if (!root) return [];
17    const res = [];
18
19    const dfs = (node, sum, path) => {
20      if (!node) return;
21      // 先把当前节点的值加入路径，再判断是否为满足条件的叶子节点
22      path.push(node.val);
23      if (node.val === sum && !node.left && !node.right) {
24        // 注意要拷贝一份，否则后续对 path 的修改会污染已收集的结果
25        res.push(path.slice());
26        return;
27      }
28      dfs(node.left, sum - node.val, path.slice());
29      dfs(node.right, sum - node.val, path.slice());
30    };
31    
32    dfs(root, sum, []);
33    return res;
34};

最近更新时间：2026-10-26

赞赏支持

题库维护不易，您的支持就是我们最大的动力！