数据结构与算法——二叉树高频题目（1）

前言：

简单记录一下自己学习算法的历程，主要根据左老师自己的视频课进行，由于大部分课程涉及题目较多，所以分文章进行记录。

本文将简单记录一下二叉树的层序遍历和 Z 形层次遍历。

参考视频：

算法讲解036【必备】二叉树高频题目-上-不含树型dp

相关题目：

力扣--102. 二叉树的层序遍历

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

关于层序遍历的学习：

重点在于 队列 的使用，和如何进行分层处理。整个算法思路同于BFS（宽度优先搜索）。我们每次只遍历当前队列长度次，确保只处理一层的数据。处理的过程中，弹出结点、加入子结点。当然也可以先处理当前层的数据，再加入新结点。队列或使用封装好的库，或直接用数组进行模拟。整体相对简单，不过多赘述。

题目解答：

1.力扣--102.二叉树的层序遍历

代码示例：

/*** 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 {
private:static constexpr int N = 2001;vector<TreeNode*> queue;int size;
public:Solution() : queue(N), size(0) {}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;int l = 0, r = 1;if(root == nullptr){return ans;}queue[0] = root;size = 1;while(size != 0){int times = size;vector<int> temp;for(int i = 0; i < times; i++){TreeNode* cur = queue[l++];size--;temp.push_back(cur->val);if(cur->left != nullptr){queue[r++] = cur->left;size++;}if(cur->right != nullptr){queue[r++] = cur->right;size++;}}ans.push_back(temp);}return ans;}
};

2.力扣--103.二叉树的锯齿形层序遍历

解题思路：

遍历层时，用reverse变量控制方向。循环时先处理同层，再添加下一层。最后更改reverse即可。

代码示例：

/*** 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 {
private:static constexpr int N = 2001;vector<TreeNode*> queue;int size;
public:Solution() : queue(N), size(0) {}vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans;if(root == nullptr){return ans;}int l = 0, r = 1;size = 1;queue[0] = root;bool reverse = false;//false -> 从左向右//true  -> 从右向左while(size != 0){vector<int> temp;int times = size;//先处理当前层，得到对应数组for(int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < times; i += j, k++){//i 表示需要遍历的起始位置下标//j 表示增量，是向左还是向右//k 用于控制循环次数TreeNode* cur = queue[i];temp.push_back(cur->val);}ans.push_back(temp);//构建下一层for(int i = 0; i < times; i++){TreeNode* cur = queue[l++];size--;if(cur->left != nullptr){queue[r++] = cur->left;size++;}if(cur->right != nullptr){queue[r++] = cur->right;size++;}}//记得更改方向reverse = !reverse;}return ans;}
};

最后，文章主要用于个人记录，如有错误还望指出和海涵，感谢阅读 ^_^