LCOF 32 - III. 从上到下打印二叉树 III
1. 问题
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
提示:
节点总数 <= 1000
2. 解法
2.1 Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
/**
* 利用双端队列两头都可以添加元素的性质,假设打印列表tmp为双端队列,规定:
* 1. 偶数层的结点添加到队列头部
* 2. 奇数层的结点添加到队列尾部
*/
// 借助队列存储将要遍历的结点
Queue<TreeNode> queue = new LinkedList<>();
// 层次遍历的结果
List<List<Integer>> res = new ArrayList<>();
// 判断当前处于什么层,初始化为奇数层
boolean isOdd = true;
// 判空
if (root == null)
return res;
// 首先把根节点加入到队列中
queue.add(root);
// 队列为空时结束循环
while (!queue.isEmpty()) {
/**
* 定义一个双端队列用于存储当前层次的打印结果:
* 1. 偶数层的结点添加到队列头部
* 2. 奇数层的结点添加到队列尾部
*/
LinkedList<Integer> deque = new LinkedList<>();
// 遍历当前层次的所有结点(即 queue 里的所有结点)
for (int i=queue.size();i>0;i--) {
// 取出 queue 的队头结点作为当前遍历结点
TreeNode curNode = queue.poll();
// 判断此时处于奇数层还是偶数层
if (isOdd)
deque.addLast(curNode.val); // 奇数层结点添加到双端队列尾部
else
deque.addFirst(curNode.val); // 偶数层结点添加到双端队列头部
// 判断当前结点是否存在左右结点,如果存在就加入到 queue 中等下一层继续遍历
if (curNode.left != null)
queue.add(curNode.left);
if (curNode.right != null)
queue.add(curNode.right);
}
// 把当前层次的遍历结果加入到 res 中
res.add(deque);
// 奇变偶 偶变奇
isOdd = !isOdd;
}
return res;
}
}
2.2 Kotlin
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun levelOrder(root: TreeNode?): List<List<Int>> {
/**
* 利用双端队列两头都可以添加元素的性质,假设打印列表tmp为双端队列,规定:
* 1. 偶数层的结点添加到队列头部
* 2. 奇数层的结点添加到队列尾部
*/
// 借助队列存储将要遍历的结点
val queue = LinkedList<TreeNode>()
// 层次遍历的结果
val res = ArrayList<List<Int>>()
// 判断当前处于什么层,初始化为奇数层
var isOdd = true
// 判空
if (root == null)
return res
// 首先把根节点加入到队列中
queue.add(root)
// 队列为空时结束循环
while (!queue.isEmpty()) {
/**
* 定义一个双端队列用于存储当前层次的打印结果:
* 1. 偶数层的结点添加到队列头部
* 2. 奇数层的结点添加到队列尾部
*/
val deque = LinkedList<Int>()
// 遍历当前层次的所有结点(即 queue 里的所有结点)
for (i in queue.size downTo 1) {
// 取出 queue 的队头结点作为当前遍历结点
val curNode = queue.poll()
// 判断此时处于奇数层还是偶数层
if (isOdd)
deque.addLast(curNode.`val`) // 奇数层结点添加到双端队列尾部
else
deque.addFirst(curNode.`val`) // 偶数层结点添加到双端队列头部
// 判断当前结点是否存在左右结点,如果存在就加入到 queue 中等下一层继续遍历
if (curNode.left != null)
queue.add(curNode.left)
if (curNode.right != null)
queue.add(curNode.right)
}
// 把当前层次的遍历结果加入到 res 中
res.add(deque)
// 奇变偶 偶变奇
isOdd = !isOdd
}
return res
}
}
2.3 复杂度分析
时间复杂度
O(N)
:N 为二叉树的结点数量,广度优先搜索需要循环 N 次,时间复杂度为O(N)
。双端队列的队首队尾的添加和删除操作的时间复杂度均为O(1)
。空间复杂度
O(N)
:最差情况下,树为满二叉树时,最多会有N/2
个结点在queue
中,需要占用O(N)
大小的额外空间。
假设满二叉树的层数为 k ,那么总结点数为 ,叶子结点的个数为 。
3. 参考
4. 标签
BFS
树
最后更新于
这有帮助吗?