437 路径总和 III

一、题目

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二、题解

方法一：DFS + 前缀和（推荐）

思路：DFS + HashMap + 前缀和。

1. 核心思路

由于路径可以从任意节点开始，因此不能像普通路径和一样只从根节点统计。

可以利用前缀和思想：

设当前从根节点到当前节点的路径和为 sum。

如果之前某个祖先节点的前缀和为：

sum - targetSum

那么这两个前缀和之间的路径和就是：

sum - (sum - targetSum) = targetSum

因此使用一个 HashMap：

key：前缀和
value：该前缀和出现次数

DFS 遍历过程中：

  • 到达当前节点时计算新的前缀和；
  • 查询 HashMap 是否存在 sum-targetSum；
  • 如果存在，则说明找到若干条合法路径；
  • 将当前前缀和加入 HashMap；
  • 递归左右子树；
  • 回溯时删除当前前缀和，避免影响其它分支。

2. 具体步骤

  1. 创建 HashMap，初始化 0 -> 1。
  2. DFS 遍历整棵树，同时维护当前路径和 sum。
  3. 查询 sum-targetSum 出现次数，并累加答案。
  4. 当前前缀和加入 HashMap。
  5. 递归左右子树。
  6. 返回父节点前，将当前前缀和出现次数减一（回溯）。

3. 关键逻辑

sum += node.val;

// 查询满足条件的前缀和
ans += map.getOrDefault(sum - target, 0);

// 当前前缀和加入HashMap
map.put(sum, map.getOrDefault(sum, 0) + 1);

// DFS左右子树
dfs(node.left, sum, target, map);
dfs(node.right, sum, target, map);

// 回溯
map.put(sum, map.get(sum) - 1);

解释：

  • 当前路径和为 sum；
  • 如果存在前缀和 sum-target；
  • 那么这两者之间的路径和就是 target；
  • DFS 返回父节点时需要恢复 HashMap，保证 HashMap 中始终只保存当前路径上的前缀和。

4. 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {

    private int ans = 0;

    public int pathSum(TreeNode root, int targetSum) {

        Map<Long, Integer> map = new HashMap<>();

        // 前缀和为0出现一次
        map.put(0L, 1);

        dfs(root, 0L, targetSum, map);

        return ans;
    }

    private void dfs(TreeNode node, long sum, int target,
                     Map<Long, Integer> map) {

        if (node == null) {
            return;
        }

        // 当前路径和
        sum += node.val;

        // 查询满足条件的前缀和
        ans += map.getOrDefault(sum - target, 0);

        // 当前前缀和加入HashMap
        map.put(sum, map.getOrDefault(sum, 0) + 1);

        // DFS左右子树
        dfs(node.left, sum, target, map);
        dfs(node.right, sum, target, map);

        // 回溯
        map.put(sum, map.get(sum) - 1);
    }
}

5. 复杂度分析

时间复杂度：O(n)

说明：每个节点仅访问一次，每次 HashMap 操作都是 O(1)

空间复杂度：O(n)

说明：HashMap 最多保存当前路径上的所有前缀和，最坏情况下需要 O(n) 空间

方法二：双层 DFS（暴力）

思路：对于每一个节点，都将其作为路径起点进行 DFS。

1. 核心思路

由于路径可以从任意节点开始。

因此：

第一层 DFS：

遍历整棵树，把每个节点作为起点。

第二层 DFS：

统计以当前节点开始的所有路径中，有多少条路径和等于 targetSum。

虽然思路简单，但是会重复计算大量路径，因此效率较低。

2. 具体步骤

  1. DFS 遍历所有节点。
  2. 每访问一个节点，就调用一次 count()。
  3. count() 不断减去当前节点值。
  4. 如果剩余目标值等于当前节点值，则答案加一。
  5. 继续递归左右子树。
  6. 所有节点统计结束返回答案。

3. 关键逻辑

return count(root, targetSum)
        + pathSum(root.left, targetSum)
        + pathSum(root.right, targetSum);

解释：

  • count() 负责统计以当前节点作为起点的路径数量；
  • pathSum(left) 统计左子树；
  • pathSum(right) 统计右子树；
  • 三部分相加就是最终答案。

4. 代码

class Solution {

    public int pathSum(TreeNode root, int targetSum) {

        if (root == null) {
            return 0;
        }

        return count(root, targetSum)
                + pathSum(root.left, targetSum)
                + pathSum(root.right, targetSum);
    }

    private int count(TreeNode node, long target) {

        if (node == null) {
            return 0;
        }

        int res = 0;

        if (node.val == target) {
            res++;
        }

        res += count(node.left, target - node.val);
        res += count(node.right, target - node.val);

        return res;
    }
}

5. 复杂度分析

时间复杂度：O(n²)

说明：每个节点都可能作为起点再次遍历整棵子树，最坏情况下退化为 O(n²)

空间复杂度：O(h)

说明：递归调用栈深度为树的高度，最坏情况下为 O(n)，平衡树情况下为 O(log n)

评论