二叉树的锯齿形层序遍历
# 📃 题目描述
题目链接:
# 🔔 解题思路
# 方法一:队列 + reverse
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 记录行号
int row = 1;
while (!queue.isEmpty()) {
int sz = queue.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < sz; i ++) {
TreeNode cur = queue.poll();
list.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
// 偶数行逆序
if (row % 2 == 0) {
Collections.reverse(list);
}
res.add(list);
// 行号 ++
row ++;
}
return res;
}
}
# 方法二:双栈
- 维护两个栈,一个存放奇数层的节点,一个存放偶数层的节点
- 分奇数层和偶数层处理
- 偶数层按顺序,每次奇数层的栈处理下一层偶数层的孩子节点,先存左结点,这样等下次 pop 时就是右节点先打印
- 奇数层反序,每次偶数层的栈处理下一层奇数层节点,先存右结点,这样等下次 pop 时就是左节点先打印
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
// 存储奇数层节点
Stack<TreeNode> stack1 = new Stack<>();
stack1.push(root);
// 存储偶数层节点
Stack<TreeNode> stack2 = new Stack<>();
while (!stack1.isEmpty() || !stack2.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
if (!stack1.isEmpty()) {
int size = stack1.size();
for (int i = 0; i < size; i ++) {
TreeNode cur = stack1.pop();
list.add(cur.val);
if (cur.left != null) {
stack2.push(cur.left);
}
if (cur.right != null) {
stack2.push(cur.right);
}
}
}
else if (!stack2.isEmpty()) {
int size = stack2.size();
for (int i = 0; i < size; i ++) {
TreeNode cur = stack2.pop();
list.add(cur.val);
// 注意这里是先 push cur.right
if (cur.right != null) {
stack1.push(cur.right);
}
if (cur.left != null) {
stack1.push(cur.left);
}
}
}
res.add(list);
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10