剑指 Offer 32 - II. 从上到下打印二叉树 II
2024-10-10 10:14:35
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
一、遍历（BFS）
本题首先要设置一个队列queue，一个list，一个临时列表。
算法流程大概如下：
首先把头结点放入queue，然后再把头结点放入tmp，最后放入list。
然后把左/右节点依次放入队列，再放入tmp，最后再放入list。
大概的思路，就是tmp作为辅助列表，作为队列queue和list的桥梁。
然后什么叫BFS，得解释一下，是二叉数的广度优先搜索的意思。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
//如果头节点不为空，则放入队列queue
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
//设置一个辅助数组，专门装队列queue的值
List<Integer> tmp = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
二、递归
class Solution {
List<List<Integer>> res;
public List<List<Integer>> levelOrder(TreeNode root) {
res = new ArrayList<>();
dfs(0, root);
return res;
}
void dfs(int depth,TreeNode root) {
if (root == null) return;
if (depth == res.size()) {//如果数组list的size等于数组里面depth的话，则创建新的一层节点
res.add(new ArrayList<>());
}
//因为dfs(0,root) 所以这个时候是res.get(0).add(root.val)，是放入这个数组中第一个数组的头节点
res.get(depth).add(root.val);
//递归遍历左右节点
dfs(depth + 1, root.left);
dfs(depth + 1, root.right);
}
}
最新文章
- Azure PowerShell (5) 使用Azure PowerShell创建简单的Azure虚拟机和Linux虚拟机
- 18.有一个网页地址, 比如PHP开发资源网主页: http://www.phpres.com/index.html,如何得到它的内容?
- Bool 类型变量的使用
- 分享45个android实例源码，很好很强大
- PS 使用首记 修改png图片的颜色
- Spring的qualifier标签
- unity 4.x 从入门到精通（持续更新）
- syntax error: missing ';' before identifier 'IWebBrowser'
- angularjs sortbale
- 关于tableView刷新
- Rich IntelliSense for jQuery
- 有关各个版本的Visual Studio（VS）和SQL Server安装的顺序总结
- angular2 官方demo heroApp
- 《java入门第一季》之类（Object类）
- TP5 model层 返回的对象转数组
- pygame 笔记-2 模仿超级玛丽的弹跳
- python 全栈开发，Day86(上传文件,上传头像,CBV,python读写Excel,虚拟环境virtualenv)
- Velocity.js初识
- powerdesigner反转数据库的设计图
- 流媒体技术学习笔记之（四）解决问题video.js 播放m3u8格式的文件,根据官方的文档添加videojs-contrib-hls也不行的原因解决了