Sum Root to Leaf Numbers

简介: Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

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.

有3个这个类型的题了,Path Sum ,Path Sum II还有这个

 

本来想直接传流的,但是流好像只能传递引用,所以最后还是传递了vector

C++代码实现:

#include<iostream>
#include<new>
#include<vector>
#include<sstream>
#include<cstdlib>
using namespace std;

//Definition for binary tree
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    int sumNumbers(TreeNode *root) {
        vector<int> vec;
        vector<int> tmp;
        int sum=0;
        hasPathSum(root,vec,tmp);
        for(auto a:vec)
           sum+=a;
        return sum;
    }
//path传入引用是因为,每一个对path的操作都要有影响,而tmp作为参数传入,是因为将上层的修改带入下层,但是下层对tmp的修改不会影响上层的操作
    void hasPathSum(TreeNode *root,vector<int> &path,vector<int> tmp)
    {
        if(root==NULL)
            return;
        tmp.push_back(root->val);
        if(root->left==NULL&&root->right==NULL)
        {
            stringstream ss;
            for(size_t i=0;i<tmp.size();i++)
                ss<<tmp[i];
            string s=ss.str();
            int c=atoi(s.c_str());
            path.push_back(c);
        }
        if(root->left)
            hasPathSum(root->left,path,tmp);
        if(root->right)
            hasPathSum(root->right,path,tmp);
    }
    void createTree(TreeNode *&root)
    {
        int i;
        cin>>i;
        if(i!=0)
        {
            root=new TreeNode(i);
            if(root==NULL)
                return;
            createTree(root->left);
            createTree(root->right);
        }
    }
};
int main()
{
    Solution s;
    TreeNode *root;
    s.createTree(root);
    int sum=s.sumNumbers(root);
    cout<<sum<<endl;
}

运行结果:

 

相关文章
|
6天前
Elasticsearch【问题记录 02】【不能以root运行es + max virtual memory areas vm.max_map_count [65530] is too low处理】
【4月更文挑战第12天】Elasticsearch【问题记录 02】【不能以root运行es + max virtual memory areas vm.max_map_count [65530] is too low处理】
23 3
|
6月前
Leetcode 623. Add One Row to Tree
题目很简单,在树的第d层加一层,值为v。递归增加一层就好了。代码如下
26 0
报错FileSystemException: /datas/nodes/0/indices/gtTXk-hnTgKhAcm-8n60Jw/1/index/.es_temp_file
首先我碰到的问题是服务器突然断电导致elasticsearch宕机,当我再次启动的时候 >FileSystemException: /data/elasticsearchDatas/datas/nodes/0/indices/gtTXk-hnTgKhAcm-8n60Jw/1/index/.es_temp_file: 结构需要清理
150 0
报错FileSystemException: /datas/nodes/0/indices/gtTXk-hnTgKhAcm-8n60Jw/1/index/.es_temp_file
LeetCode 222. Count Complete Tree Nodes
给出一个完全二叉树,求出该树的节点个数。
67 0
LeetCode 222. Count Complete Tree Nodes
|
Go
LeetCode 124. Binary Tree Maximum Path Sum
给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
52 0
LeetCode 124. Binary Tree Maximum Path Sum
|
人工智能
Tree with Maximum Cost---CF1092F 树上DP
You are given a tree consisting exactly of n vertices. Tree is a connected undirected graph with n−1 edges. Each vertex v of this tree has a value av assigned to it. Let dist(x,y) be the distance between the vertices x and y.
120 0
Tree with Maximum Cost---CF1092F 树上DP
|
Oracle 关系型数据库 索引
20180316不使用INDEX FULL SCAN (MIN/MAX)
[20180316]为什么不使用INDEX FULL SCAN (MIN/MAX).txt --//链接:http://www.itpub.net/thread-2100456-1-1.
1177 0
|
SQL Oracle 关系型数据库
|
ARouter 网络协议
Node Joining Process in 6LoWPAN - ND, RPL
https://ez.analog.com/docs/DOC-12488 In typical 6LoWPAN networks, the registration is normally referred to as the node joining process.
1506 0