鏈接

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

思路

本題和113.路徑總和II是類似的思路，做完這道題，可以順便把113.路徑總和II 和 112.路徑總和 做了。

結合112.路徑總和 和 113.路徑總和II，我在講了二叉樹：遞歸函數究竟什么時候需要返回值，什么時候不要返回值？，如果大家對二叉樹遞歸函數什么時候需要返回值很迷茫，可以看一下。

接下來在看本題，就簡單多了，本題其實需要使用回溯，但一些同學可能都不知道自己用了回溯，在二叉樹：以為使用了遞歸，其實還隱藏著回溯中，我詳細講解了二叉樹的遞歸中，如何使用了回溯。

接下來我們來看題：

首先思路很明確，就是要遍歷整個樹把更節點到葉子節點組成的數字相加。

那么先按遞歸三部曲來分析：

遞歸三部曲

如果對遞歸三部曲不了解的話，可以看這里：二叉樹：前中后遞歸詳解

• 確定遞歸函數返回值及其參數

這里我們要遍歷整個二叉樹，且需要要返回值做邏輯處理，所有返回值為void，在二叉樹：遞歸函數究竟什么時候需要返回值，什么時候不要返回值？中，詳細講解了返回值問題。

參數只需要把根節點傳入，此時還需要定義兩個全局遍歷，一個是result，記錄最終結果，一個是vector path。

「為什么用vector類型（就是數組）呢？ 因為用vector方便我們做回溯！」

所以代碼如下：

int result; vector<int> path; void traversal(TreeNode* cur)

• 確定終止條件

遞歸什么時候終止呢？

當然是遇到葉子節點，此時要收集結果了，通知返回本層遞歸，因為單條路徑的結果使用vector，我們需要一個函數vectorToInt把vector轉成int。

終止條件代碼如下：

if (!cur->left && !cur->right) { // 遇到了葉子節點result += vectorToInt(path);return; }

這里vectorToInt函數就是把數組轉成int，代碼如下：

int vectorToInt(const vector<int>& vec) {int sum = 0;for (int i = 0; i < vec.size(); i++) {sum = sum * 10 + vec[i];}return sum; }

• 確定遞歸單層邏輯

本題其實采用前中后序都不無所謂， 因為也沒有中間幾點的處理邏輯。

這里主要是當左節點不為空，path收集路徑，并遞歸左孩子，右節點同理。

「但別忘了回溯」。

如圖：

代碼如下：

// 中 if (cur->left) { // 左 （空節點不遍歷）path.push_back(cur->left->val);traversal(cur->left); // 遞歸path.pop_back(); // 回溯 } if (cur->right) { // 右 （空節點不遍歷）path.push_back(cur->right->val);traversal(cur->right); // 遞歸path.pop_back(); // 回溯 }

這里要注意回溯和遞歸要永遠在一起，一個遞歸，對應一個回溯，是一對一的關系，有的同學寫成如下代碼：

if (cur->left) { // 左 （空節點不遍歷）path.push_back(cur->left->val);traversal(cur->left); // 遞歸 } if (cur->right) { // 右 （空節點不遍歷）path.push_back(cur->right->val);traversal(cur->right); // 遞歸 } path.pop_back(); // 回溯

「把回溯放在花括號外面了，世界上最遙遠的距離，是你在花括號里，而我在花括號外！」 這就不對了。

整體C++代碼

關鍵邏輯分析完了，整體C++代碼如下：

class Solution { private:int result;vector<int> path;// 把vector轉化為intint vectorToInt(const vector<int>& vec) {int sum = 0;for (int i = 0; i < vec.size(); i++) {sum = sum * 10 + vec[i];}return sum;}void traversal(TreeNode* cur) {if (!cur->left && !cur->right) { // 遇到了葉子節點result += vectorToInt(path);return;}if (cur->left) { // 左 （空節點不遍歷）path.push_back(cur->left->val);traversal(cur->left); // 遞歸path.pop_back(); // 回溯}if (cur->right) { // 右 （空節點不遍歷）path.push_back(cur->right->val);traversal(cur->right); // 遞歸path.pop_back(); // 回溯}return ;} public:int sumNumbers(TreeNode* root) {path.clear();if (root == nullptr) return 0;path.push_back(root->val);traversal(root);return result;} };

總結

過于簡潔的代碼，很容易讓初學者忽視了本題中回溯的精髓，甚至作者本身都沒有想清楚自己用了回溯。

我這里提供的代碼把整個回溯過程充分的提現出來，希望可以幫助大家看的明明白白！

本文：

https://github.com/youngyangyang04/leetcode-master?github.com

已經收錄，里面還有leetcode刷題攻略、各個類型經典題目刷題順序、思維導圖，可以fork到自己倉庫，有空看一看一定會有所收獲，如果對你有幫助也給一個star支持一下吧！ 我的B站（里面有我講解的算法視頻已經編程相關知識）：

嗶哩嗶哩 ( ゜- ゜)つロ 乾杯~ Bilibili?space.bilibili.com

我是程序員Carl，哈工大師兄，先后在騰訊和百度從事技術研發多年，利用工作之余重刷leetcode，更多精彩算法文章盡在：代碼隨想錄，關注后，回復「Java」「C++」「python」「簡歷模板」等等，有我整理多年的學習資料，可以加我微信，備注「個人簡介」+「組隊刷題」，拉你進入刷題群，每天一道經典題目分析，我選的每一道題目都不是孤立的，而是由淺入深一脈相承的，如果跟住節奏每篇連續著看，定會融會貫通。

總結

以上是生活随笔為你收集整理的消除左递归c++代码_「leetcode」129. 求根到叶子节点数字之和【递归中隐藏着回溯】详解...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。