有LeetCode交流群/华为OD考试扣扣交流群可加：948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练
文章目录
题目链接题目描述解题思路DFS和BFS异同用队列维护的BFS
代码PythonJavaC++时空复杂度
相关习题华为OD算法/大厂面试高频题算法练习冲刺训练
题目链接
LeetCode103、二叉树的锯齿形层序遍历
题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[[15,7],[20,9],[3]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
树中节点数目在范围 [0, 2000] 内-1000 <= Node.val <= 1000
解题思路
DFS和BFS异同
二叉树层序遍历是一个非常经典的问题，属于必须掌握的题目。
所谓二叉树遍历（traversal）指的是按照一定次序系统地访问一棵二叉树，使每个节点恰好被访问一次。
二叉树遍历实质上是二叉树的线性化，将树状结构变为线性结构。
二叉树遍历有两大类：
深度优先（depth first traversal，DFS）：先完成一棵子树的遍历再完成另一棵广度优先（breath first traversal，BFS）：先完成一层节点的遍历再完成下一层
DFS和BFS均为树/图的搜索方式，能够访问树/图中的所有节点。它们的特点可以从以下的比喻看出区别：
DFS：优先移动节点，当对给定节点尝试过每一种可能性之后，才退到前一节点来尝试下一个位置。就像一个搜索者尽可能地深入调查未知的地域，直到遇到死胡同才回头。（下图以前序遍历为例）
BFS：优先对给定节点的下一个位置进行进行尝试，当对给定节点尝试过每一种可能性之后，才移动到下一个节点。就像一只搜索军队铺展开来覆盖领土，直到覆盖了所有地域。
用队列维护的BFS
树的广度优先遍历亦可称为层序遍历。其核心特点为，从上到下、从左到右访问树中的节点，每一层的节点都按顺序出现。
本题就是二叉树BFS的板子题，必须掌握。
BFS通常需要通过维护一个先进先出 （First In First Out，FIFO) 的队列来实现。
我们需要构建一个队列q用于储存每一层的所有节点，然后执行while循环（循环不变量为q不为空）：
获得当前队列长度qSize，为该层的节点个数初始化一个空的子列表subList，用于储存二叉树该层所有节点的值执行for循环，循环qSize次。每一次循环包含以下环节 a. 令队列q的队头节点出队，记为node，并将其值node.val存入subList中 b. 若node的左孩子node.left存在，则令node.left从队尾入队 c. 若node的右孩子node.right存在，则令node.right从队尾入队 （这些后入队的节点会在下一层的遍历中被取出）经过qSize次循环后，subList已经储存了这一层节点的所有值，将subList加入全局的答案变量ans中
这样就就是二叉树BFS的基本过程，其中第3步是最关键的步骤。
如果题目有明显地要求区分每一层的情况（比如本题要求每一层的节点值需要单独储存在一个子列表中），则循环qSize次这个步骤是必要的。
本题沿用了LeetCode102、二叉树的层序遍历的大体框架，但最后要求返回的结果是自底向上的层序遍历，只需要返回ans数组的反转即可。即
return ans[::-1]
代码
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root == None:
return []
ans = list()
q = deque()
q.append(root)
# False表示当前需要从左往右；True表示当前需要从右往左
flag = False
while q:
qSize = len(q)
subList = list()
for _ in range(qSize):
node = q.popleft()
subList.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if flag == False:
ans.append(subList)
else:
ans.append(subList[::-1])
flag = not flag
return ans
Java
class Solution {
public List
List
if (root == null) {
return ans;
}
Deque
q.offer(root);
boolean flag = false;
while (!q.isEmpty()) {
int qSize = q.size();
List
for (int i = 0; i < qSize; i++) {
TreeNode node = q.poll();
subList.add(node.val);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
if (flag) {
reverse(subList);
}
ans.add(subList);
flag = !flag;
}
return ans;
}
private void reverse(List
int left = 0, right = list.size() - 1;
while (left < right) {
int temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
left++;
right--;
}
}
}
C++
class Solution {
public:
vector
vector
if (root == nullptr) {
return ans;
}
queue
q.push(root);
bool flag = false;
while (!q.empty()) {
int qSize = q.size();
vector
for (int i = 0; i < qSize; ++i) {
TreeNode* node = q.front();
q.pop();
subList.push_back(node->val);
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
if (flag) {
reverse(subList.begin(), subList.end());
}
ans.push_back(subList);
flag = !flag;
}
return ans;
}
};
时空复杂度
时间复杂度：O(N)。仅需一次遍历整棵树。
空间复杂度：O(M)。M为层的最大节点数，队列所占空间。
相关习题
LeetCode101、对称二叉树
LeetCode102、二叉树的层序遍历
LeetCode103、二叉树的锯齿形层序遍历
LeetCode107、二叉树的层序遍历II
LeetCode199、二叉树的右视图
LeetCode429、N叉树的层序遍历
LeetCode513、找树左下角的值
LeetCode515、在每个树行中找最大值
LeetCode637、二叉树的层平均值
LeetCode655、输出二叉树
LeetCode662、二叉树的最大宽度
LeetCode993、二叉树的堂兄弟节点
LeetCode1161、最大层内元素和
LeetCode1302、层数最深叶子节点的和
LeetCode1609、奇偶树
华为OD算法/大厂面试高频题算法练习冲刺训练
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
推荐文章
您阅读本篇文章共花了：
发表评论