[LeetCode] 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.

这道求根到叶节点数字之和的题跟之前的求Path Sum 二叉树的路径和很类似,都是利用DFS递归来解,这道题由于不是单纯的把各个节点的数字相加,而是每到一个新的数字,要把原来的数字扩大10倍之后再相加。代码如下:

/**
 * 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) {
        return sumNumbersDFS(root, 0);
    }
    int sumNumbersDFS(TreeNode *root, int sum) {
        if (!root) return 0;
        sum = sum * 10 + root->val;
        if (!root->left && !root->right) return sum;
        return sumNumbersDFS(root->left, sum) + sumNumbersDFS(root->right, sum);
    }
};

本文转自博客园Grandyang的博客,原文链接:求根到叶节点数字之和[LeetCode] Sum Root to Leaf Numbers ,如需转载请自行联系原博主。

相关文章
|
8月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
11月前
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 357. Count Numbers with Unique Digits
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。
63 0
LeetCode 357. Count Numbers with Unique Digits
|
存储 Python
LeetCode 315. Count of Smaller Numbers After Self
给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
75 0
LeetCode 315. Count of Smaller Numbers After Self
|
存储
Leetcode-Medium 2. Add Two Numbers
Leetcode-Medium 2. Add Two Numbers
52 0
Leetcode-Easy 985. Sum of Even Numbers After Queries
Leetcode-Easy 985. Sum of Even Numbers After Queries
80 0
LeetCode解题之二:Add Two Numbers
LeetCode解题之二:Add Two Numbers