[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 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-二叉搜索树与双向链表

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 思路一: 由于要求链表是有序...

2563
来自专栏nnngu

算法09 五大查找之:哈希查找

前面的几篇文章分别总结了:顺序查找、二分查找、索引查找、二叉排序树。这一篇文章要总结的是五大查找的最后一个:哈希查找(也称为散列查找)。提起哈希,我的第一印象就...

2819
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

2716
来自专栏前端说吧

JS - 二叉树算法实现与遍历 (更新中...)

2758
来自专栏尾尾部落

[剑指offer] 二叉树的下一个结点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

601
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

40510
来自专栏mathor

堆及其相关应用

 提到堆就不得不说到二叉树这个结构,堆就是一颗完全二叉树,什么叫完全二叉树,用一句话来概括就是:设二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,...

772
来自专栏IT可乐

Java数据结构和算法(十)——二叉树

  接下来我们将会介绍另外一种数据结构——树。二叉树是树这种数据结构的一员,后面我们还会介绍红黑树,2-3-4树等数据结构。那么为什么要使用树?它有什么优点? ...

2106
来自专栏青玉伏案

算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中...

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

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

3387

扫码关注云+社区