437. 路径总和 III

题解：DFS

/*** 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:long long rootSum(TreeNode* root, long long targetSum){if(!root){return 0;}int res = 0;if(root->val == targetSum){res ++;}res += rootSum(root->left, targetSum - root->val);res += rootSum(root->right, targetSum - root->val);return res;} long long pathSum(TreeNode* root, long long targetSum){if(!root){return 0;}int res = rootSum(root, targetSum);res += pathSum(root->left, targetSum);res += pathSum(root->right,targetSum);return res;}
};

题解-通俗易懂

发现AI讲题还挺有意思。单独加上一个 Section。

想象一下，你在一棵大树上寻宝，这棵树的每个树枝节点上都标有一个数字。你的任务是找到所有从某个节点出发，往下走，路径上所有数字加起来正好等于“目标宝藏值”（targetSum）的路线有多少条。

重要规则：这个路线不一定非要从最顶端的树根开始，也不一定非要走到最末端的叶子。它可以从任何一个节点开始，到它下面的任何一个节点结束。

这段代码用了“分工合作”的策略，设计了两个函数来完成这个任务：

1. rootSum：一个“专一的探路者”。

2. pathSum：一个“总指挥官”。

---

1. rootSum 函数详解 (专一的探路者)

rootSum 的任务非常简单和专一：它只负责寻找那些【必须】从当前我给它的这个节点 (root) 出发的寻宝路线。

我们来看看它是怎么工作的：

codeC++

long long rootSum(TreeNode* root, long long targetSum){// 如果这个节点是空的（路到头了），那肯定没路可走，返回 0 条。if(!root){return 0;}int res = 0; // 准备一个计数器，记录找到了几条路// 1. 先看看我自己是不是一个宝藏？//    就我一个节点，不多也不少，如果我的值正好等于目标值，那恭喜，找到了一条！if(root->val == targetSum){res++;}// 2. 接下来，我要把路往下延伸，去我的左子树里继续找。//    既然我已经走了我这一步 (root->val)，那么接下来的路需要凑够的数就是 `targetSum - root->val`。//    于是我喊来另一个 `rootSum` 小分队，告诉它：“喂，从我的左孩子出发，帮我找找和为 `targetSum - root->val` 的路有多少条？”res += rootSum(root->left, targetSum - root->val);// 3. 同理，我也要去我的右子树里继续找。//    我也喊来另一个 `rootSum` 小分队，让它从我的右孩子出发，继续完成剩下的任务。res += rootSum(root->right, targetSum - root->val);// 把上面三步找到的路线总数加起来，就是从我这个节点出发的所有寻宝路线数量。return res;
}

rootSum 的小结： 你给它一个起点和一个目标值，它就勤勤恳恳地从这个起点往下走，告诉你从这个起点出发，有多少条路线的和恰好是那个目标值。

---

2. pathSum 函数详解 (总指挥官)

pathSum 的任务是总揽全局。它知道寻宝路线可以从 任何一个节点 开始，而 rootSum 只会从指定的节点开始。那怎么办呢？

很简单，pathSum 就遍历树上的每一个节点，然后对每一个节点都说：“喂，rootSum，现在轮到你上场了，把这个节点当做起点，去给我找路！”

我们来看看它的指挥过程：

codeC++

long long pathSum(TreeNode* root, long long targetSum){// 如果整棵树都是空的，那肯定一条路都没有。if(!root){return 0;}// 这里的总路线数，可以分成三个部分：// 1. 从【当前这个根节点】出发的路线。// 2. 完全在【左子树】内部的路线 (起点和终点都在左子树里)。// 3. 完全在【右子树】内部的路线 (起点和终点都在右子树里)。// 第一部分：让 `rootSum` 这个专家出马，计算一下从当前 `root` 节点出发的路线有多少条。int res = rootSum(root, targetSum);// 第二部分：我不管从当前节点出发的路了，我去它的左子树里看看。// 对左子树来说，它也是一棵完整的树，里面也可能藏着各种寻宝路线。// 于是我对自己下了一个同样的命令（递归调用）：“喂，另一个我，去左子树里执行一遍完整的 `pathSum` 任务！”res += pathSum(root->left, targetSum);// 第三部分：同理，我也要去右子树里执行一遍完整的 `pathSum` 任务。res += pathSum(root->right, targetSum);// 把这三部分找到的路线数量全部加起来，就是最终的答案。return res;
}