【面试经典 150 | 二叉树层序遍历】二叉树的锯齿形层序遍历

本文主要是介绍【面试经典 150 | 二叉树层序遍历】二叉树的锯齿形层序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：层序遍历+双端队列
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【二叉树】【层序遍历】【双端队列】

题目来源

103. 二叉树的锯齿形层序遍历

解题思路

方法一：层序遍历+双端队列

思路

本题不同于其他进行层序遍历二叉树的题目，我们还要将每一层的节点值存储下来，并且相邻层的节点值存储顺序不同。比如这一层的节点值是从左到右存储，那么下一层的节点值是从右往左存储。

为此，我们可以使用一个数组按从左往右顺序存储，如果需要从右往左存储，则逆序即可。

我们再想一想，从左往右存储节点值实际上就是在数组后增加值，从右往左存储节点就是在数组前增加节点值，这就是双端队列的 push_back 和 push_front 啊。于是我们可以使用双端队列来存储不同顺序的节点值。

注意，我们还需要维护一个 bool 变量 isOrderLeft 用来表示当前是按照从左往右还是从右往左的顺序存储节点值。我们初始化 isOrderLeft = true 表示双端队列的 push_back 操作，即从左往右存储。如果 isOrderLeft = false，则表示双端队列的 push_front 操作，即从右往左存储。

代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans;if (root == NULL)return ans;queue<TreeNode*> q;q.push(root);bool isOrderLeft = true;while (!q.empty()) {deque<int> leaves;int size = q.size();for (int i = 0; i < size; ++i) {TreeNode *curr = q.front(); q.pop();if (isOrderLeft)leaves.push_back(curr->val);elseleaves.push_front(curr->val);if (curr->left)q.push(curr->left);if (curr->right)q.push(curr->right);}ans.emplace_back(vector<int>(leaves.begin(), leaves.end()));isOrderLeft = !isOrderLeft;}return ans;}
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 为二叉树中的节点数，每个节点会仅会被遍历一次。

空间复杂度： $O (n)$ ，我们需要维护存储节点的队列和存储节点值的双端队列。