Binary Tree Level Order Traversal II——LeetCode
2024-09-17 16:42:39
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7}
,
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
题目大意为,按照层次逆序输出每一层的节点,很明显用层次遍历即可,之前在Minimum Depth of Binary Tree ——LeetCode这个题目中,也用到了层次遍历,下面先看我写的,也是用upRow,downRow,来记录上一层、下一层的节点数量,upRow--为0时,一层遍历完了。
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<Integer> level = new LinkedList<>();
List<List<Integer>> res = new LinkedList<>();
if (root == null)
return res;
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int upRow = 1, downRow = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.getFirst();
queue.removeFirst();
if (node.left != null) {
queue.add(node.left);
downRow++;
}
if (node.right != null) {
queue.add(node.right);
downRow++;
}
upRow--;
level.add(node.val);
if (upRow == 0) {
res.add(0, level);
level = new LinkedList<>();
upRow = downRow;
downRow=0;
}
}
return res;
}
后来发现一种更巧妙的解,就是利用queue的size(),根本不用记录这两个值。
Talk is cheap>>
public List<List<Integer>> levelOrderBottom2(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> wrapList = new LinkedList<>(); if (root == null) return wrapList;
queue.offer(root);
while (!queue.isEmpty()) {
int levelNum = queue.size();
List<Integer> subList = new LinkedList<>();
//把一层元素全部取出
for (int i = 0; i < levelNum; i++) {
TreeNode node = queue.poll();//取出队列第一个元素
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
subList.add(node.val);
}
wrapList.add(0, subList);
}
return wrapList;
}
最新文章
- 用python+selenium抓取微博24小时热门话题的前15个并保存到txt中
- Nginx密码验证 ngx_http_auth_basic_module模块
- Jenkins_获取源码编译并启动服务(一)
- 请问如何查看mysql 的端口号?
- eclipse中新建jni工程
- 11. Container With Most Water
- 【HDU1402】【FFT】A * B Problem Plus
- SASS type-of 函数
- OAuth认证的过程
- Python 2.7 学习笔记 列表的使用
- 有关Flash中与Java调用时候注意的一些事项
- web app 基础界面框架搭建
- 移动端WEBAPP开发遇到的坑,以及填坑方案!持续更新~~~~
- SpriteKit给游戏弹跳角色添加一个高度标示器
- python TextMining
- Putting Boxes Together CodeForces - 1030F (带权中位数)
- golang channel select
- python练习题-day3
- 16个PHP设计模式详解
- linux strace追踪mysql执行语句 (mysqld --debug)
热门文章
- Qt 属性
- GCOV 使用用例
- Java基础知识强化之IO流笔记05:try...catch...finally包含的代码是运行期的
- android自定义listview实现圆角
- Asp.net 菜单控件
- [转]delphi 删除动态数组的指定元素
- 你好,C++(36)人参再好,也不能当饭吃!6.3 类是如何面向对象的
- Javascript深度克隆一个对象
- 开始编写正式的iOS 程序(iOS编程指导)
- The ultimate jQuery Plugin List(终极jQuery插件列表)