目录
题目
在【JZ-32-II】的基础上，要求打印每一层的方向交替变化，即，奇数层正序打印，偶数层倒序打印。
参考
方法一-层序遍历+双端队列
算法思路
算法流程：
1. 特例处理： 根节点
r
o
o
t
root
root 为空时，直接返回空列表
2. 初始化： 结果列表
r
e
s
res
res 和 包含根节点的双端队列
d
e
q
u
e
deque
deque
3. BFS循环，当队列
d
e
q
u
e
deque
deque 为空时跳出循环：
- 新建一个临时列表 t m p tmp tmp，用来存储当前这层的打印结果；
- 当前层打印循环（循环次数为当前层节点数，即
d
e
q
u
e
deque
deque 长度）：
队首元素出队，记为 n o d e node node；
打印该元素，若为奇数层，则将 n o d e . v a l node.val node.val 添加到列表 t m p tmp tmp 尾部；若为偶数层，则将 n o d e . v a l node.val node.val 添加到列表 t m p tmp tmp 头部；
若 n o d e node node 的左右子节点不为空，则将子节点加入队列 d e q u e deque deque - 将当前层打印结果 t m p tmp tmp 转化为 list 并添加到结果列表 r e s res res
4. 返回值： 结果列表 r e s res res
关于如何判断奇数层还是偶数层：
res.size()为偶数时，当前层为奇数层； res.size()为奇数时，当前层为偶数层
具体代码
/**
* 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) {
Deque<TreeNode> deque = new LinkedList<>();//双端队列初始化
List<List<Integer>> res = new ArrayList<>();//结果列表初始化
if(root != null)deque.offerLast(root);//根节点尾部入队
while(!deque.isEmpty()){
LinkedList<Integer> tmp = new LinkedList<>();//临时列表，存储当前层的打印结果
for(int i = deque.size(); i > 0; i--){
TreeNode node = deque.pollFirst();//队首元素出队
if(res.size() % 2 == 0)tmp.offerLast(node.val);//奇数层，列表尾部添加
else tmp.offerFirst(node.val);//偶数层，列表头部添加
//子节点入队
if(node.left != null)deque.offerLast(node.left);
if(node.right != null)deque.offerLast(node.right);
}
res.add(tmp);//当前层打印结果添加到结果列表
}
return res;
}
}
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)，n 为二叉树节点总数。因为 BFS 需要循环 n 次，双端队列的队首和队尾添加操作、删除操作的时间复杂度均为 O ( 1 ) O(1) O(1)
- 空间复杂度： O ( n ) O(n) O(n)，因为在最坏情况下，即，树为平衡二叉树时，最多会有 n / 2 n/2 n/2 个节点同时在队列 d e q u e deque deque 中，占用了 O ( n ) O(n) O(n) 大小的额外空间。
方法二-奇偶层逻辑分离
算法思路
在方法一的基础上，将奇偶层逻辑拆分，消除冗余的判断（方法一中需要判断每一个节点所在层的奇偶性）
算法流程（只有BFS循环部分与方法一不同）：
BFS循环，当队列 d e q u e deque deque 为空时跳出循环：
- 打印奇数层：从左向右打印，先左后右加入下层节点；
- 打印偶数层：从右向左打印，先右后左加入下层节点；
具体代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();//双端队列初始化
List<List<Integer>> res = new ArrayList<>();//结果列表初始化
if(root != null)deque.offerLast(root);//根节点尾部入队
while(!deque.isEmpty()){
//打印奇数层
LinkedList<Integer> tmp = new LinkedList<>();//临时列表，存储当前层的打印结果
for(int i = deque.size(); i > 0; i--){
//从左向右打印
TreeNode node = deque.pollFirst();//队首元素出队
tmp.offerLast(node.val);
//先左后右加入下层节点
if(node.left != null)deque.offerLast(node.left);
if(node.right != null)deque.offerLast(node.right);
}
res.add(tmp);//当前层打印结果添加到结果列表
if(deque.isEmpty())break;//若队列为空提前跳出
//打印偶数层
tmp = new LinkedList<>();
for(int i = deque.size(); i > 0; i--){
//从右向左打印
TreeNode node = deque.pollLast();//队尾元素出队
tmp.offerLast(node.val);
//先右后左加入下层节点
if(node.right != null)deque.offerFirst(node.right);
if(node.left != null)deque.offerFirst(node.left);
}
res.add(tmp);//当前层打印结果添加到结果列表
}
return res;
}
}
复杂度分析
同方法一
方法三-层序遍历+倒序
算法思路
将偶数层中的元素倒序
具体代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();//双端队列初始化
List<List<Integer>> res = new ArrayList<>();//结果列表初始化
if(root != null)deque.offerLast(root);//根节点尾部入队
while(!deque.isEmpty()){
//打印奇数层
LinkedList<Integer> tmp = new LinkedList<>();//临时列表，存储当前层的打印结果
for(int i = deque.size(); i > 0; i--){
TreeNode node = deque.pollFirst();//队首元素出队
tmp.offerLast(node.val);
//加入下层节点
if(node.left != null)deque.offerLast(node.left);
if(node.right != null)deque.offerLast(node.right);
}
if(res.size() % 2 == 1)Collections.reverse(tmp);//偶数层倒序
res.add(tmp);//当前层打印结果添加到结果列表
}
return res;
}
}
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)，n 为二叉树节点总数。因为 BFS 需要循环 n 次，占用 O ( n ) O(n) O(n)；一共进行了少于 n 个节点的倒序操作，占用 O ( n ) O(n) O(n)。
- 空间复杂度： O ( n ) O(n) O(n)，因为在最坏情况下，即，树为满二叉树时，最多会有 n / 2 n/2 n/2 个节点同时在队列 d e q u e deque deque 中，占用了 O ( n ) O(n) O(n) 大小的额外空间。