[LeetCode] Sum Root to Leaf Numbers

魏明发布于2019-08-16 11:16 / 951人阅读

Problem

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.

Note: A leaf is a node with no children.

Example

Input: [1,2,3]

    1
   / 
  2   3

Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:

Input: [4,9,0,5,1]

Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution

class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        return sum(root, 0);
    }
    private int sum(TreeNode root, int cur) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return cur*10+root.val;
        return sum(root.left, cur*10+root.val)+sum(root.right, cur*10+root.val);
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71120.html

[Leetcode-Tree] Sum Root to Leaf Numbers

摘要：解题思路本题要求所有从根结点到叶子节点的路径和，我们用递归实现。结束条件当遇到叶子节点时，直接结束，返回计算好的如果遇到空节点，则返回数值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...

BigNerdCoding 2019-08-16 10:27 评论0 收藏0
[Leetcode] Sum Root to Leaf Numbers 累加叶子节点

摘要：递归法复杂度时间空间递归栈空间思路简单的二叉树遍历，遍历时将自身的数值加入子节点。一旦遍历到叶子节点便将该叶子结点的值加入结果中。 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...

wean 2019-08-14 16:10 评论0 收藏0
[LeetCode] Path Sum (I & II & III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

张金宝 2019-08-19 11:09 评论0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 评论0 收藏0
LeetCode 之 JavaScript 解答第112题 —— 路径总和（Path Sum）

摘要：小鹿题目路径总和给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明叶子节点是指没有子节点的节点。 Time：2019/4/26Title: Path SumDifficulty: EasyAuthor: 小鹿题目：Path Sum（路径总和） Given a binary tree and a sum, determin...

lylwyy2016 2019-08-26 13:44 评论0 收藏0