[Leetcode] Sum Root to Leaf Numbers 累加叶子节点

wean 发布于2019-08-14 16:10 / 587人阅读

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

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.

递归法 复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

简单的二叉树遍历，遍历时将自身的数值加入子节点。比如节点A的值是1，其左子节点的值是2，则将左子节点变为12。一旦遍历到叶子节点便将该叶子结点的值加入结果中。

代码

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

海外云主机 GPU服务器除了root节点 Numbers Leaf LeetCode

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

转载请注明本文地址：https://www.ucloud.cn/yun/66158.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] Path Sum I & II & III 路径和1,2,3

摘要：只要我们能够有一个以某一中间路径和为的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。最新更新请见：https://yanjia.me/zh/2019/01/... Path Sum I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that addin...

caiyongji 2019-08-14 12:25 评论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
[LeetCode] Sum Root to Leaf Numbers

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 tota...

魏明 2019-08-16 11:16 评论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