专栏首页米扑专栏【leetcode】Sum Root to Leaf Numbers

【leetcode】Sum Root to Leaf Numbers

Question:

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.

Anwser 1:  

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void calSum(TreeNode *root, int val, int &sum){
        if(root == NULL){
            return;
        }
        
        if(root->left == NULL && root->right == NULL){
            sum += root->val + val * 10;
            return;
        }
        
        calSum(root->left, val * 10 + root->val, sum);
        calSum(root->right, val * 10 + root->val, sum);
    }
    
    int sumNumbers(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int sum = 0;
        
        calSum(root, 0, sum);
        
        return sum;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Binary Tree Maximum Path Sum

    Given a binary tree, find the maximum path sum.

    阳光岛主
  • Linux / MacOS 修改 ls 显示年月日的时间格式

    本文参考转自米扑博客:Linux / MacOS 修改 ls 显示年月日的时间格式

    阳光岛主
  • 【leetcode】Path Sum

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc...

    阳光岛主
  • 【leetcode刷题】T123-路径总和

    https://leetcode-cn.com/problems/path-sum

    木又AI帮
  • LeetCode 1339. 分裂二叉树的最大乘积(DP)

    给你一棵二叉树,它的根为 root 。请你删除 1 条边,使二叉树分裂成两棵子树,且它们子树和的乘积尽可能大。

    Michael阿明
  • LeetCode 965. Univalued Binary Tree

    A binary tree is univalued if every node in the tree has the same value.

    Angel_Kitty
  • 递归遍历-LeetCode 124、112、113(递归遍历二叉树,回溯法)

    给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

    算法工程师之路
  • Flat风格的Qml组合框

    Qt君
  • LeetCode 669 Trim a Binary Search Tree

    给定二叉搜索树以及 L和 R 最低和最高边界作为修剪树,使其所有元素都在[L, R](R> = L). 您可能需要更改树的根,因此结果应返回修剪后的二叉搜索树的...

    一份执着✘
  • 337. 打家劫舍 III Krains 2020-08-05 10:18:45 动态规划

    Krains

扫码关注云+社区

领取腾讯云代金券