消除左递归c++代码_「leetcode」129. 求根到叶子节点数字之和【递归中隐藏着回溯】详解...

链接

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. 求根到叶子节点数字之和【递归中隐藏着回溯】详解...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。