【leetcode刷题笔记】Sum Root to Leaf Numbers
2024-08-30 01:34:06
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
.
题解:
一开始的想法是计算每个节点到叶节点可以得到的整数的列表,然后返回给该节点的父节点,然后通过这个列表计算父节点到叶节点可以生成的整数,但是这种方法有个问题就是在计算父节点*10^x+子节点到页节点生成的整数的时候不能确定x的值,因为不知道父节点到叶节点的距离。所以这种方法不可行。
后来想了下,有个更简单的方法:将最终生成的整数存放在叶节点而不是根节点。每次递归的时候,在当前节点计算一个sum,表示从根节点到当前节点生成的整数,然后把这个sum传递给当前节点的孩子,在孩子上递归的计算从根节点到孩子节点生成的整数.....
举个例子,如下图所示的一棵树:
最后将各个节点上的sum相加(123+125+146)就得到了最终的答案。
代码如下:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int totalSum = 0;
private void rootList(TreeNode root,int sum){
if(root == null)
return;
sum = sum*10+root.val; if(root.left == null && root.right == null)
{
totalSum += sum;
return;
} rootList(root.left, sum);
rootList(root.right, sum); }
public int sumNumbers(TreeNode root) {
rootList(root, 0);
return totalSum;
}
}
最新文章
- 百度地图开发 Android版应用Key申请
- JavaScript星形评分
- Beta版本——第七次冲刺博客
- Java中面向对象的详解
- openVPN使用
- Android开发系列之ListView
- 如何在WebSocket类中访问Session
- LeeCode-Same Tree
- Linux用户及用户组管理
- c++中的 堆和栈
- iOS网络模块优化(失败重发、缓存请求有网发送)
- bash与ksh数组使用
- 戏说春秋_i春秋 writeup
- Python特技杂货铺
- Delphi之TComponent类
- Linux内核分析——第五章 系统调用
- C# 数组&;集合&;泛型集合
- Ng第八课:神经网络表述(Neural Networks: Representation)
- hdu 5073 有坑+方差贪心
- spring not_support 该方法被事务方法调用时 不会加入spring事务 只是执行jdbc普通的事务