HHot 100C++ 图解

437. 路径总和 III

中等 二叉树 在力扣上做

一句话套路树上前缀和 + 哈希(Q560 的树版)

题目描述

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

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

 

示例 1:

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

示例 2:

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

 

提示:

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

思路

时间O(n)
空间O(n)

思路

路径必须「向下」但起终点任意 -> 等价于树上任意一条根向链上的子段和,

于是套用 Q560

DFS 维护根到当前的前缀和 cur,查有多少祖先的前缀和 = cur-target。

回溯时必须 cnt[cur]--(离开这条分支要把状态还回去),这是树上前缀和的命门。

对比

双重 DFS(每个结点都当一次起点)是 O(n^2)。若结点值全为非负,可以在「向下累积和已超过 target」时剪枝;但本题允许 -1000 ≤ val ≤ 1000,往下走不保证和变大,所以必须一路探到底 —— 这才是它需要前缀和的原因。

图解

3 3 -2 5 2 1 10 -3 11
二叉树(来自本仓库测试数据,nullopt 表示空位)

C++17 题解

src/08_binary_tree.cpp23 行
namespace lc0437 {
class Solution {
 public:
  int pathSum(TreeNode* root, int targetSum) {
    unordered_map<long long, int> cnt;
    cnt[0] = 1;  // 空前缀:从根出发的路径
    return dfs(root, 0, (long long)targetSum, cnt);
  }

 private:
  static int dfs(TreeNode* n, long long cur, long long target,
                 unordered_map<long long, int>& cnt) {
    if (!n) return 0;
    cur += n->val;
    int ans = cnt[cur - target];       // 以 n 为终点、起点是某祖先的路径条数
    ++cnt[cur];
    ans += dfs(n->left, cur, target, cnt);
    ans += dfs(n->right, cur, target, cnt);
    --cnt[cur];                        // 回溯!兄弟分支不该看到这条路径的前缀和
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q437_path_sum_iii10 行
lc0437::Solution s;
TreeNode* a = buildTree({10, 5, -3, 3, 2, nullopt, 11, 3, -2, nullopt, 1});
CHECK_EQ(s.pathSum(a, 8), 3);  // 5->3, 5->2->1, -3->11
TreeNode* b = buildTree({5, 4, 8, 11, nullopt, 13, 4, 7, 2, nullopt, nullopt, nullopt, 1});
// 注意路径起点不必是根:5->4->11->2 与 4->11->7 都算,共 2 条
// (同一棵树用 Q112/113「根到叶」只会有 1 条,这就是两者的区别)
CHECK_EQ(s.pathSum(b, 22), 2);
CHECK_EQ(s.pathSum(nullptr, 0), 0);
freeTree(a);
freeTree(b);

↑↓ 选择↵ 打开/ 随时唤起