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

【解释】 给一颗二叉树,要求返回其从根结点到叶子结点组成数字之和。从根结点到叶子结点从上到下对应从左到右。例如路径1->2,则代表数字为12. 【思路】 基本上和Path Sum II同样的思路,上篇博文也有。思路基本相同,只不过在找到满足条件的子集之后,本题要做的是加和。

public class Solution {
    private int sum=0;
    public int getNum(List<Integer> list){//得到所在list所有值的正数表示
        int res=0;
        for(int i=0;i<list.size();i++){
            res=res*10+list.get(i);
        }
        return res;
    }
    public void sumNumbersCore(List<Integer> list, TreeNode root){
        list.add(root.val);
        if(root.left==null&&root.right==null)
            sum+=getNum(list);//将所有路径代表的数字累加
        else{
            if(root.left!=null)
                sumNumbersCore(list,root.left);
            if(root.right!=null)
                sumNumbersCore(list,root.right);
        }
        list.remove(list.size()-1);
    }
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;//空树
        List<Integer> list=new ArrayList<Integer>();
        sumNumbersCore(list,root);
        return sum;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

Leetcode|二叉树非递归版后序遍历

二叉树的非递归版后序遍历,首先定义TreeNode如下: """ TreeNode class """ class TreeNode(object): ...

3174
来自专栏C/C++基础

给定入栈序列,判断出栈序列是否合法

题目:分别给定入栈序列和出栈序列,然后判断出栈序列是否合法。如入栈序列是[1,3,2,4,5],出栈序列[3,1,2,4,5]是合法的,[3,1,5,2,4]是...

542
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

2394
来自专栏小二的折腾日记

牛客网-剑指offer-2

二叉树是觉得很烦的东西了,比链表复杂很多,看着头都有点疼啊,但是没办法,生活就是这样,只有把不会的会了才会进步,怕的变得不怕才能越来越厉害。 常规的理解一下:二...

1352
来自专栏用户画像

4.5.3 哈弗曼树(Huffman)树和哈弗曼编码

树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的...

471
来自专栏数据结构与算法

2977 二叉堆练习1

2977 二叉堆练习1 时间限制: 10 s 空间限制: 32000 KB 题目等级 : 白银 Silver 题目描述 Description 已...

2416
来自专栏数据结构与算法

2010 求后序遍历

2010 求后序遍历 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一...

3116
来自专栏wym

树状数组理论基础

  树状数组(binary indexed trees,二进制索引树),最早由Peter M. Fenwick于1994年以“A New Data Struct...

602
来自专栏彭湖湾的编程世界

【算法】堆排序学习笔记

参考资料 《算法(第4版)》          — — Robert Sedgewick, Kevin Wayne 什么是二叉堆 在了解堆排序之前, 最重要的当...

2228
来自专栏书山有路勤为径

排序数组转换为二叉查找树

已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

683

扫码关注云+社区