【递归】11. leetcode 129 求根节点到叶节点数字之和

1 题目描述

题目链接：
求根节点到叶节点数字之和

2 解答思路

第一步：挖掘出相同的子问题  （关系到具体函数头的设计）
第二步：只关心具体子问题做了什么  （关系到具体函数体怎么写，是一个宏观的过程）
第三步：找到递归的出口，防止死递归  （关系到如何跳出递归）

2.1 相同的子问题（函数头设计）

相同的子问题：求根节点到叶节点数字之和，就是求左子树到叶子节点数字之和 加上 右子树到叶子节点数字之和

重点：

这里的相同子问题，是左子树到叶子节点数字之和 加上 右子树到叶子节点数字之和。

和我之前写的题解不一样，之前都是分开递归，这里要一起递归。

下面是leetcode给的函数头

int sumNumbers(TreeNode* root) {}

传入一个二叉树，最终返回根节点到叶节点数字之和。

2.1.1 第一种方法

根据之前分析的相同的子问题，这里需要传入两个参数，分别是二叉树以及和

设计的函数头如下：

 int dfs(TreeNode* root, int sum){}

2.1.2 第二种方法

可以不用返回 二叉树的左子树到叶子节点的和 加上 该二叉树的右子树到叶子节点的和

而是单纯的计算出每一条路径走完之后sum的值，然后将sum的值保存在全局变量vector中，最终在主函数中遍历一遍vector,将vector中的值全部加起来，加到ret中。返回ret的值。

这样的方式，具体子问题递归的时候就会发生变化，下面文章我会写。

2.2 具体的子问题做了什么（函数体的实现）

2.2.1 第一种方法

根据之前的分析，具体的子问题做的事情：
1.计算sum的值：将sum的值乘以10，并加上当前节点的值。sum = sum * 10 + root->val;
2.如果是叶子节点，返回sum的值（这也是递归的出口）
3.如果不是叶子节点，就继续计算该二叉树的左子树到叶子节点的和 加上 该二叉树的右子树到叶子节点的和

    int dfs(TreeNode* root, int sum){if (root == nullptr)return 0;sum = sum * 10 + root->val;if (root->left == nullptr && root->right == nullptr)return sum;return dfs(root->left, sum) + dfs(root->right, sum);}

2.2.2 第二种方法

根据之前的分析，具体的子问题做的事情：
1.计算sum的值：将sum的值乘以10，并加上当前节点的值。sum = sum * 10 + root->val;
2.如果是叶子节点，将sum插入到vector的后面，并直接退出函数（这也是递归的出口）
3.如果不是叶子节点，就继续计算该二叉树的左子树到叶子节点的和 以及 该二叉树的右子树到叶子节点的和

    void dfs(TreeNode* root, int sum){if (root == nullptr)return;sum = sum * 10 + root->val;if (root->left == nullptr && root->right == nullptr){nums.push_back(sum);return;}dfs(root->left, sum);dfs(root->right, sum);}

3 总结

3.1 第一种方法

class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root, 0);}int dfs(TreeNode* root, int sum){if (root == nullptr)return 0;sum = sum * 10 + root->val;if (root->left == nullptr && root->right == nullptr)return sum;return dfs(root->left, sum) + dfs(root->right, sum);}
};

3.2 第二种方法

class Solution {
public:vector<int> nums;int sumNumbers(TreeNode* root) {int sum = 0;dfs(root, sum);int ret = 0;for (int i = 0; i < nums.size(); ++ i){ret += nums[i];}return ret;}void dfs(TreeNode* root, int sum){if (root == nullptr)return;sum = sum * 10 + root->val;if (root->left == nullptr && root->right == nullptr){nums.push_back(sum);return;}dfs(root->left, sum);dfs(root->right, sum);}
};