📝 题目描述

题目链接：路径总和 III

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

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

示例：

示例 1：

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示：

  • 二叉树的节点个数的范围是 [0,1000]
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

💡 解题思路

方法一：前缀和✅️

实际上就是“和为K的子数组”的变体。

定义节点的前缀和为：由根结点到当前结点的路径上所有节点的和。我们利用先序遍历二叉树，记录下根节点 root 到当前节点 p 的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 pre 减去 targetSum。

值得注意的是，对于空路径我们也需要保存预先处理一下，此时因为空路径不经过任何节点，因此它的前缀和为 0；
同时，由于我们顺着左侧的分支走到底，然后退回父节点准备去探索右侧的新分支时，左侧分支深处节点所产生的前缀和，对于右侧分支来说是不存在的（因为路径只能从上往下），所以在回溯时要清除哈希表中的记录。

方法二：暴力解法

使用深度优先搜索穷举所有的可能，我们访问每一个节点 nodenode，检测以 nodenode 为起始节点且向下延深的路径有多少种。我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。

  • 我们首先定义 rootSum(p,val)rootSum(p,val) 表示以节点 pp 为起点向下且满足路径总和为 valval 的路径数目。我们对二叉树上每个节点 pp 求出 rootSum(p,targetSum)rootSum(p,targetSum)，然后对这些路径数目求和即为返回结果。
  • 我们对节点 pp 求 rootSum(p,targetSum)rootSum(p,targetSum) 时，以当前节点 pp 为目标路径的起点递归向下进行搜索。假设当前的节点 pp 的值为 valval，我们对左子树和右子树进行递归搜索，对节点 pp 的左孩子节点 pl​p_l​ 求出 rootSum(pl​,targetSum−val)rootSum(p_l​,targetSum−val)，以及对右孩子节点 prp_r​ 求出 rootSum(pr​,targetSum−val)rootSum(p_r​,targetSum−val)。节点 pp 的 rootSum(p,targetSum)rootSum(p,targetSum) 即等于 rootSum(pl​,targetSum−val)rootSum(p_l​,targetSum−val) 与 rootSum(pr​,targetSum−val)rootSum(p_r​,targetSum−val) 之和，同时我们还需要判断一下当前节点 pp 的值是否刚好等于 targetSumtargetSum。
  • 我们采用递归遍历二叉树的每个节点 pp，对节点 pp 求 rootSum(p,val)rootSum(p,val)，然后将每个节点所有求的值进行相加求和返回。

🔧 代码实现

1、前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    unordered_map<int64_t, int64_t> mp;
    void searchPath(int64_t pre, TreeNode* root, int targetSum) {
        if (!root) return;
        pre += root -> val;
        if (mp.count(pre - targetSum)) {
            ans += mp[pre - targetSum];
        }
        mp[pre]++;
        searchPath(pre, root -> left, targetSum);
        searchPath(pre, root -> right, targetSum);
        mp[pre]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        mp[0] = 1;
        searchPath(0, root, targetSum);
        return ans;
    }
};

2、暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int rootSum(TreeNode* root, long long targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};

📊 复杂度分析

1、前缀和

  • 时间复杂度：O(N)O(N)，其中 N 是二叉树的节点数。深度优先搜索的递归确保了每个节点只会被遍历一次，且哈希表的查询和插入操作平均时间复杂度都是 O(1)O(1)，所以整体时间复杂度是线性的。
  • 空间复杂度：O(N)O(N)，主要开销在于递归调用的系统栈空间（最坏情况下树退化为链表，深度为 N）以及哈希表占用的空间（最多存储 N 个不同的前缀和）。

2、暴力解法

  • 时间复杂度：O(N2)O(N_2)，其中 N 为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(N)O(N)，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 O(N2)O(N_2)。
  • 空间复杂度：O(N)O(N)，考虑到递归需要在栈上开辟空间。

🎯 总结

  • 核心思想：本质上还是两数之和的变体，掌握前缀和的思路很重要。