LeetCode129—Sum Root to Leaf Numbers

雨点打透心脏的1/2处 2022-09-21 13:11 113阅读 0赞

# LeetCode129—Sum Root to Leaf Numbers #

## 原题 ##

[https://leetcode.com/problems/sum-root-to-leaf-numbers/][https_leetcode.com_problems_sum-root-to-leaf-numbers]

> Given a binary tree containing digits from 0-9 only, each root-to-leaf path could >represent a number.
> 
> An example is the root-to-leaf path 1->2->3 which represents the number 123.
> 
> Find the total sum of all root-to-leaf numbers.
> 
> For example,
> 
> 1  
> / \\  
> 2 3  
> The root-to-leaf path 1->2 represents the number 12.  
> The root-to-leaf path 1->3 represents the number 13.
> 
> Return the sum = 12 + 13 = 25.

意思就是说，所有从根到叶子节点的路径上构成的数加起来的和。

--------------------

## 分析 ##

过程如下：

> 1.首先求出根到叶子节点的所有路径  
> 2.计算路径中包含节点所代表的数字  
> 3.把所有路径的结果加起来

直接dfs解决即可。

### **代码** ###

class Solution {
    private:
        void dfs(TreeNode *root, vector<int>tmp, int&sum);
    public:
        int sumNumbers(TreeNode* root) {
            int sum = 0;
            vector<int>tmp;
            dfs(root, tmp, sum);
            return sum;
        }
    };
    void Solution::dfs(TreeNode *root,vector<int>tmp,int &sum)
    {
        if (root == NULL)
        {
            return;
        }
        if (root->left == NULL && root->right == NULL)//叶子节点
        {
            tmp.push_back(root->val);
            int tmpsum = 0;
            for (int i = 0; i < tmp.size(); i++)
            {
                tmpsum = tmpsum * 10 + tmp[i];//计算path值
            }
            sum += tmpsum;
            return;
        }
        tmp.push_back(root->val);
        dfs(root->left,tmp,sum);
        dfs(root->right, tmp,sum);
    }

[https_leetcode.com_problems_sum-root-to-leaf-numbers]: https://leetcode.com/problems/sum-root-to-leaf-numbers/