剑指 Offer 32 – III. 从上到下打印二叉树
本问题对应的 leetcode 原文链接:剑指 Offer 32 – III. 从上到下打印二叉树
本次对应打卡任务:【二叉树专题】多次考察真题:剑指 Offer 32 – III. 从上到下打印二叉树
问题描述
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[20,9],
[15,7]
]
提示:
节点总数 <= 1000
解题思路
视频讲解直达: 本题视频讲解
代码实现
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
int sum = 1;
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = 0; i < k; i++){
TreeNode t = queue.poll();
if(sum % 2 = = 1){
tmp.add(t.val);
} else {
tmp.addFirst(t.val);
}
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(tmp);
sum ++;
}
return res;
}
}
时间复杂度:O(n)
额外空间复杂度:容器里最对存放 1/2 的节点,故为 O(n)
评论(4)
1
使用双端队列,用res来判断偶数奇数层,偶数层是从尾部出队,奇数层时从头部出队
时间复杂度on
使用Collections偶数行反转?(学的)
使用LinkedList特性模拟双端队列
时间复杂度 O(N) : N 为二叉树的节点数量,即 BFS 需循环 N 次,占用 O(N) ;双端队列的队首和队尾的添加和删除操作的时间复杂度均为 O(1)
空间复杂度 O(N) : 最差情况下,即当树为满二叉树时,最多有 N/2 个树节点 同时 在 deque 中,使用 O(N) 大小的额外空间。
优化,一次循环奇数偶数层同时进行
奇数层:从左向右打印,先左后右加入下层节点
偶数层:从右向左打印,先右后左加入下层节点