Day93 | 灵神 | 二叉树 求根节点到叶结点数字之和

129.求根节点到叶结点数字之和

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

先序遍历思路：

这道题和昨天那道Day92 | 灵神 | 二叉树 路径总和-CSDN博客的区别就是我们要在走这些路径的时候要想办法把当前正在走的路径的数字给算出来

然后昨天那道题是在叶节点处把flag改为true，证明我们找到了一条路径满足条件

今天这个题是在叶子结点时，把你加好的这条路径的和返回给上一级递归函数

而我们如何在路径图中计算数字呢？

设一开始是x=0，那么每经过一个结点就让x*10加上当前结点的值就好了

然后在叶子结点处进行返回就好了

先看先序遍历（dfs）的代码吧

可以先看看比较差但是能跑通的笔者的代码

我是用字符串把路径数字都存起来然后在叶子结点处转化为整数再加起来，感觉这个方法笨笨的对比灵神的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int res=0;
    void tra(TreeNode* t,string path)
    {
        if(t==nullptr)
            return ;
        char temp=t->val+'0';
        path.push_back(temp);
        if(t->left==nullptr&&t->right==nullptr)
            res+=atoi(path.c_str());
        tra(t->left,path);
        tra(t->right,path);
    }
    int sumNumbers(TreeNode* root) {
        tra(root,"");
        return res;
    }
};

/*lambda版本
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res=0;
        function<void(TreeNode*,string)> tra=[&](TreeNode* t,string path)->void
        {
            if(t==nullptr)
            return ;
            char temp=t->val+'0';
            path.push_back(temp);
            if(t->left==nullptr&&t->right==nullptr)
                res+=atoi(path.c_str());
            tra(t->left,path);
            tra(t->right,path);
        };
        tra(root,"");
        return res;
    }
};*/

这是灵神的代码，就是按照上面的思路写的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        auto dfs = [&](this auto&& dfs, TreeNode* node, int x) -> void {
            if (node == nullptr) {
                return;
            }
            x = x * 10 + node->val;
            if (node->left == node->right) { // node 是叶子节点
                ans += x;
                return;
            }
            dfs(node->left, x);
            dfs(node->right, x);
        };
        dfs(root, 0);
        return ans;
    }
};

再看看不用额外变量res记录，直接返回答案的代码

我个人觉得这个最好了，本层逻辑就是

1.算x

2.判断是不是叶子，是的话返回x

3.最后返回左子树的数字之和，右子树的数字之和两者相加的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int tra(TreeNode *t,int x)
    {
        if(t==nullptr)
            return 0;
        x=x*10+t->val;
        if(t->left==nullptr&&t->right==nullptr)
            return x;
        return tra(t->left,x)+tra(t->right,x);
    }
    int sumNumbers(TreeNode* root) {
        return tra(root,0);
    }
};

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
    int tra(TreeNode *t,int x)
    {
        if(t==nullptr)
            return 0;
        x=x*10+t->val;
        if(t->left==nullptr&&t->right==nullptr)
            return x;
        return tra(t->left,x)+tra(t->right,x);
    }
    int sumNumbers(TreeNode* root) {
        return tra(root,0);
    }
};

/*class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        auto dfs = [&](this auto&& dfs, TreeNode* node, int x) -> void {
            if (node == nullptr) {
                return;
            }
            x = x * 10 + node->val;
            if (node->left == node->right) { // node 是叶子节点
                ans += x;
                return;
            }
            dfs(node->left, x);
            dfs(node->right, x);
        };
        dfs(root, 0);
        return ans;
    }
};*/
 
/*
class Solution {
public:
    int res=0;
    void tra(TreeNode* t,string path)
    {
        if(t==nullptr)
            return ;
        char temp=t->val+'0';
        path.push_back(temp);
        if(t->left==nullptr&&t->right==nullptr)
            res+=atoi(path.c_str());
        tra(t->left,path);
        tra(t->right,path);
    }
    int sumNumbers(TreeNode* root) {
        tra(root,"");
        return res;
    }
};*/

/*lambda版本
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res=0;
        function<void(TreeNode*,string)> tra=[&](TreeNode* t,string path)->void
        {
            if(t==nullptr)
            return ;
            char temp=t->val+'0';
            path.push_back(temp);
            if(t->left==nullptr&&t->right==nullptr)
                res+=atoi(path.c_str());
            tra(t->left,path);
            tra(t->right,path);
        };
        tra(root,"");
        return res;
    }
};*/