题解 | #二叉树根节点到叶子节点的所有路径和#

二叉树根节点到叶子节点的所有路径和

http://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83

递归思想
通过题意可知,是要把从根节点到叶子节点的单一路径的数值进行拼接,拼成一个数,再把所有路径的数进行加和进行返回输出。
一般树的题都会想到的就是遍历,那么这个题也一样。首先定义一个函数,这个函数用来拼接数值以及计算加和。
拼接数值其实一句 sum=sum*10 + node->val就可以了,前提是sum初始值为0,也就是整棵树的根节点的父节点为0。那么当遍历到叶子节点后,返回sum的值即为拼接的数。之后递归遍历左、右子树,最终返回二者加和即可。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */

    int dfs(TreeNode* node, int sum)
    {
        if(!node) return 0;
        sum = sum*10 + node->val;
        if(!node->left && !node->right)
        {
            return sum;
        }
        int sum_left = dfs(node->left,sum);
        int sum_right = dfs(node->right,sum);
        return sum_left+sum_right;
    }

    int sumNumbers(TreeNode* root) {
        // write code here
        return dfs(root,0);
    }
};
牛客刷题记录 文章被收录于专栏

记录自己的刷题记录,刷过的题的解法

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 17:30
点赞 评论 收藏
分享
八股刚起步,看了javaguide,小林coding,还有面渣,感觉面渣是体验最好的,请问只看面渣够用吗,有不完善的需要补吗?
码农索隆:先背最基础的知识,然后理解情景题,现在面试大多数喜欢问情景题,更考验面试者的基础和临场发挥情况
点赞 评论 收藏
分享
牛客38347925...:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务