问题描述:
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
.
原问题链接:https://leetcode.com/problems/sum-root-to-leaf-numbers/
问题分析
这个问题的要求比较有意思,因为它要计算所有从根到叶节点构成的值,并且要将它们所有的和计算出来。从根节点到叶节点的过程相当于一个10进制的过程,每下一层,就对前面的值乘以十再加上当前层的值。
那么在实现中我们就需要想办法求到从根节点到叶节点最终形成的值。对树中间任意节点来说,我们就需要有一个对应的位置保存有到这个节点的值,然后对于它的子节点就可以用这个当前值再乘以十再相加了。为了得到这最终形成的值,我们需要对树做一个遍历,这样才能保证覆盖到所有的节点。在遍历的过程中,我们判断出所有左右子树节点都为空的节点才算是叶节点。现在的问题就是要选择哪种树遍历的方法了。我们可以选择树的层次化遍历方法,用一个队列,不断的将队列里的元素取出来,然后将它所有存在的子节点加入到队列中。前面也提到过,对应的节点也需要有一个对应的值,我们可以用另外一个队列和它同步的保存对应的值。这样每次从节点队列里取元素出来的时候,我们也取对应的值队列里的元素。如果当前节点的左右子树为空,则它符合条件,我们将它累加到一个全局的变量中。如果它有非空的节点,则将这个节点对应的值乘以十再加那个节点的值,并将这个值加入到值队列中。
按照这个思路,我们得到的详细实现如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int sumNumbers(TreeNode root) { if(root == null) return 0; int sum = 0; Queue<Integer> numQueue = new LinkedList<>(); Queue<TreeNode> nodeQueue = new LinkedList<>(); numQueue.add(root.val); nodeQueue.add(root); while(!nodeQueue.isEmpty()) { TreeNode node = nodeQueue.remove(); int num = numQueue.remove(); if(node.left == null && node.right == null) { sum += num; continue; } if(node.left != null) { nodeQueue.add(node.left); numQueue.add(num * 10 + node.left.val); } if(node.right != null) { nodeQueue.add(node.right); numQueue.add(num * 10 + node.right.val); } } return sum; } }
相关推荐
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 ...
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 ...
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
3sum 力码 力扣算法 (注:“ :locked: " 表示你需要来自 Leetcode) # 标题 解决方案 困难 001 简单的 002 中等的 003 中等的 004 难的 005 中等的 006 简单的 007 简单的 008 简单的 009 简单的 010 难的 011 中等...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode题目:Best Time to Buy and Sell Stock II
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode: ://leetcode.com/ 程式语言:C ++ # 标题 解决方案 困难 1个 简单的 2个 中等的 3 中等的 4 难的 5 中等的 6 中等的 7 反整数 7反向整数 简单的 8 字符串到整数(atoi) 8字符串到整数(atoi) ...
leetcode:leetcode刷题
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释