?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;
}