給你二叉樹的根節(jié)點 root 和一個整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點到葉子節(jié)點 路徑總和等于給定目標(biāo)和的路徑。

葉子節(jié)點 是指沒有子節(jié)點的節(jié)點。

示例 1：

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

示例 2：

輸入：root = [1,2,3], targetSum = 5
輸出：[]

示例 3：
輸入：root = [1,2], targetSum = 0
輸出：[]

提示：

樹中節(jié)點總數(shù)在范圍 [0, 5000] 內(nèi)
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

這道題其實比較好做的，但是需要打破前幾道回溯算法那樣的思路，開始就說過回溯類的題目都可以寫成N叉樹的形式，這個正好又是二叉樹，所以就很簡單了；

開始想到了for循環(huán)是不用寫的，只需要分別遞歸左右子樹就可以了，
且遍歷到葉子節(jié)點時，如果路徑所有節(jié)點和和targetSum相等，這條路徑就是答案；

但是寫出來發(fā)現(xiàn)了一個問題，當(dāng)判斷出來葉子節(jié)點后，此時的路徑path并沒有將葉子節(jié)點加進(jìn)去，sum也一樣，所以我就單獨在結(jié)束時又加了一遍并回溯結(jié)束，這樣就可以了；

而且當(dāng)root節(jié)點為空時也需要判斷，這個要寫在判斷葉子節(jié)點下面；
寫在下面也面臨一個問題就是葉子節(jié)點不能直接判斷，所以我又通過一個函數(shù)來判斷葉子節(jié)點；

詳細(xì)注釋代碼如下：

/*** 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:vector<vector<int>> ans;vector<int> path;int sum = 0;void backTracking(TreeNode *root, int targetSum) {//判斷是否為葉子節(jié)點if (isLeafnode(root)) {//為葉子節(jié)點，此時sum還沒有加上葉子節(jié)點的值，所以先加上葉子節(jié)點val看看是否和//targetSum相等，如果相等，則將最后一個節(jié)點就是葉子節(jié)點壓入path，此時path就是//答案之一，把path加入ans，然后回溯將這個葉子節(jié)點再從path里拿出來if (sum + root -> val == targetSum) {path.push_back(root -> val);ans.push_back(path);path.pop_back();}return ;}//這個判斷是為了保證節(jié)點不為空if (!root) return ;sum += root -> val;path.push_back(root -> val);backTracking(root -> left, targetSum);//向下遞歸左子樹backTracking(root -> right, targetSum);//向下遞歸右子樹path.pop_back();//回溯sum -= root -> val;//回溯}//判斷節(jié)點是否為葉子節(jié)點bool isLeafnode(TreeNode* root) {if (!root) return false;if (!root -> left && !root -> right) return true;return false;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if (!root) return ans;backTracking(root, targetSum);return ans;} };

總結(jié)

以上是生活随笔為你收集整理的113. 路径总和 （剑指 Offer 34. 二叉树中和为某一值的路径）（回溯算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。