【递归】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);
    }
};