牛客算法必刷TOP101，包含：链表、二分查找/排序、二叉树、堆/栈/队列、哈希、递归/回溯、动态规划、字符串、双指针、贪心算法、模拟总共101道题。
此部分是二叉树专题。
二叉树的前序遍历
描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
数据范围：二叉树的节点数量满足$ 0 \le n \le 100$ ，二叉树节点的值满足 $1 \le val \le 100$ ，树的各节点的值各不相同
示例 1：
解析
解析1-递归
按照前序遍历的定义，先遍历中间结点，接着遍历左孩子，在遍历右孩子。
1void preorderTraversal(vector<int> &res,TreeNode*root){
2 if(root==nullptr){
3 return ;
4 }
5 res.push_back(root->val);
6 preorderTraversal(res, root->left);
7 preorderTraversal(res, root->right);
8 }
9
10 vector<int> preorderTraversal(TreeNode* root) {
11 vector<int> res;
12 preorderTraversal(res,root);
13 return res;
14 }
解析2-迭代法
递归的方式使用到了函数栈，我们也可以自己用栈进行模拟。
对于前序遍历，我们先访问中间结点，再访问左边结点，最后访问右结点。但是根据栈的特性：先进后出。应该先放入右结点，再放入左结点。
1vector<int> preorderTraversal(TreeNode* root){
2 vector<int> res;
3 if(root==nullptr){
4 return res;
5 }
6 // 辅助栈
7 stack<TreeNode*> help;
8 help.push(root);
9 // 不为空就继续
10 while(!help.empty()){
11 TreeNode*temp = help.top();
12 help.pop();
13 res.push_back(temp->val);
14 // 要先放入右孩子
15 if(temp->right){
16 help.push(temp->right);
17 }
18 // 再放入左孩子
19 if(temp->left){
20 help.push(temp->left);
21 }
22 }
23 return res;
24}
二叉树的中序遍历
描述
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足 $0 \le n \le 1000$，树上每个节点的值满足 $0 \le val \le 1000$ 进阶：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：
1{1,2,#,#,3}
返回值：
1[2,3,1]
说明：
示例2
输入：
1{}
返回值：
1[]
示例3
输入：
1{1,2}
返回值：
1[2,1]
说明：
示例4
输入：
1{1,#,2}
返回值：
1[1,2]
说明：
解析
解析1-递归法
根据题意进行模拟
1void inorderTraversal(vector<int> &res,TreeNode* root){
2 if(root==nullptr){
3 return ;
4 }
5 if(root->left){
6 inorderTraversal(res,root->left);
7 }
8 res.push_back(root->val);
9 if(root->right){
10 inorderTraversal(res,root->right);
11 }
12 }
13 vector<int> inorderTraversal(TreeNode* root) {
14 vector<int>res;
15 inorderTraversal(res,root);
16 return res;
17 }
解析2-迭代法
由于中序遍历是先访问左孩子，我们就要先找到左孩子，一直要找到树叶的左孩子。一直深度优先找到左孩子，然后访问左孩子，之后访问中间结点，之后对右孩子进行这样迭代遍历。
1vector<int> inorderTraversal(TreeNode* root){
2 vector<int>res;
3 if(root==nullptr){
4 return res;
5 }
6 stack<TreeNode*>help;
7 while(root||!help.empty()){
8 while(root){
9 help.push(root);
10 root = root->left;
11 }
12 TreeNode*temp = help.top();
13 help.pop();
14 res.push_back(temp->val);
15 root = temp->right;
16 }
17 return res;
18}
二叉树的后序遍历
描述
给定一个二叉树，返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围：二叉树的节点数量满足 $0 \le n \le 100$，二叉树节点的值满足 $1 \le val \le 100$ ，树的各节点的值各不相同
样例图
解析
解析1-递归
根据题意进行模拟
1 void postorderTraversal(vector<int>&res,TreeNode*root){
2 if(root==nullptr){
3 return;
4 }
5 postorderTraversal(res,root->left);
6 postorderTraversal(res,root->right);
7 res.push_back(root->val);
8 }
9 vector<int> postorderTraversal(TreeNode* root) {
10 vector<int>res;
11 postorderTraversal(res,root);
12 return res;
13 }
解析2-迭代
根据后序遍历“左右中”的顺序，那么后序遍历也与中序遍历类似，要先找到每棵子树的最左端节点：
1//每次找到最左节点
2while(root != NULL){
3 s.push(root);
4 root = root->left;
5}
然后我们就要访问该节点了嘛？不不不，如果它还有一个右节点呢？根据“左右根”的原则，我还要先访问右子树。我们只能说它是最左端的节点，它左边为空，但是右边不一定，因此这个节点必须被看成是这棵最小的子树的根。要怎么访问根节点呢？
我们都知道从栈中弹出根节点，一定是左节点已经被访问过了，因为左节点是子问题，访问完了才回到父问题，那么我们还必须要确保右边也已经被访问过了。如果右边为空，那肯定不用去了，如果右边不为空，那我们肯定优先进入右边，此时再将根节点加入栈中，等待右边的子树结束。
1//该节点再次入栈
2s.push(node);
3//先访问右边
4root = node->right;
不过，当右边被访问了，又回到了根，我们的根怎么知道右边被访问了呢？用一个前序指针pre标记一下，每个根节点只对它的右节点需要标记，而每个右节点自己本身就是一个根节点，因此每次访问根节点的时候，我们可以用pre标记为该节点，回到上一个根节点时，检查一下，如果pre确实是它的右子节点，哦那正好，刚刚已经访问过了，我现在可以安心访问这个根了。
1//如果该元素的右边没有或是已经访问过
2if(node->right == NULL || node->right == pre){
3 //访问中间的节点
4 res.push_back(node->val);
5 //且记录为访问过了
6 pre = node;
7}
具体做法：
- step 1：开辟一个辅助栈，用于记录要访问的子节点，开辟一个前序指针pre。
- step 2：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
- step 3：弹出一个栈元素，看成该子树的根，判断这个根的右边有没有节点或是有没有被访问过，如果没有右节点或是被访问过了，可以访问这个根，并将前序节点标记为这个根。
- step 4：如果没有被访问，那这个根必须入栈，进入右子树继续访问，只有右子树结束了回到这里才能继续访问根。
图示：
1 vector<int> postorderTraversal(TreeNode* root) {
2 vector<int>res;
3 stack<TreeNode*>help;
4 TreeNode*pre = nullptr;
5 while(root||!help.empty()){
6 //每次先找到最左边的节点
7 while(root){
8 help.push(root);
9 root = root->left;
10 }
11 //弹出栈顶
12 TreeNode*temp = help.top();
13 help.pop();
14 //如果该元素的右边没有或是已经访问过
15 if(temp->right==nullptr||temp->right==pre){
16 //访问中间的节点
17 res.push_back(temp->val);
18 //且记录为访问过了
19 pre = temp;
20 }else{
21 //该节点入栈
22 help.push(temp);
23 //先访问右边
24 root = temp->right;
25 }
26 }
27 return res;
28 }
求二叉树的层序遍历
描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历） 例如： 给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[[3], [9,20], [15,7]]
数据范围：二叉树的节点数满足 $1 \le n \le 10^5$
解析
主要思路：广度优先，一层一层的遍历二叉树， 1、遍历到一个节点，将左右个孩子加入队列； 2、一次遍历二叉树的一层； 3、怎么确定能遍历一层：每次遍历队列，先记录队列的大小size，出队size次，这些值即为一层，存入res数组，并通过1、2将下一层的节点存入队列；
1 vector<vector<int> > levelOrder(TreeNode* root) {
2 vector<vector<int>> res;
3 if(root==nullptr){
4 return res;
5 }
6 queue<TreeNode*> q;
7 q.push(root);
8 while(!q.empty()){
9 // 对每一层都进行处理
10 int size = q.size();
11 vector<int> levelVals;
12 // 这一层右多少个结点
13 while(size--){
14
15 TreeNode* cur = q.front();
16 q.pop();
17 levelVals.push_back(cur->val);
18 // 将这层的孩子结点加入队列
19 if(cur->left){
20 q.push(cur->left);
21 }
22 if(cur->right){
23 q.push(cur->right);
24 }
25 }
26 // 这层的结果
27 res.push_back(levelVals);
28 }
29 return res;
30 }
按之字形顺序打印二叉树
描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0≤n≤1500,树上每个节点的val满足 |val| <= 1500
要求：空间复杂度：O(n)，时间复杂度：O(n)
解析
如果我们不按照之字形打印二叉树，只是按照层遍历，那么就成了层序遍历。在层序遍历中都是从左到右遍历，之字形是要相反的，先放进“队列”里面的要最后出来。如下图
可以用两个栈交替保存“父节点和子节点”。
1vector<vector<int> > Print(TreeNode* pRoot) {
2 TreeNode* head = pRoot;
3 vector<vector<int>> res;
4 if(head==nullptr){
5 return res;
6 }
7 // 交替保存 父亲节点和子节点
8 stack<TreeNode*> cen;
9 stack<TreeNode*> children;
10 cen.push(head);
11 // 如果有一个不为空就可以执行
12 while(!cen.empty() || !children.empty()){
13 vector<int> temp;
14 // 父亲节点有 这里的父亲节点和子节点是相对的，由于这里一次可以遍历两层，所以第一层就是父亲节点，
15 while(!cen.empty()){
16 TreeNode*node = cen.top();
17 temp.push_back(node->val);
18 // 父亲节点，是从左到右 要先从左孩子判断
19 if(node->left){
20 children.push(node->left);
21 }
22 if(node->right){
23 children.push(node->right);
24 }
25 cen.pop();
26 }
27 if(temp.size()){
28 res.push_back(temp);
29 }
30 temp.clear();
31 // 孩子不为空就是
32 while(!children.empty()){
33 TreeNode*node = children.top();
34 temp.push_back(node->val);
35 // 偶数层是从右向左遍历的，要先开始判断右边的。
36 if(node->right){
37 cen.push(node->right);
38 }
39 if(node->left){
40 cen.push(node->left);
41 }
42 children.pop();
43 }
44 if(temp.size()){
45 res.push_back(temp);
46 }
47 }
48 return res;
49 }
总结
刷题时间
| 时间 | 题目 |
|---|---|
| 5-3 | 前序遍历 |
| 5-3 | 中序遍历 |
| 5-3 | 后序遍历 |
| 5-4 | 层序遍历 |
| 6-22 | 按之字形打印二叉树 |
总结
- 前序遍历要先遍历中间结点，之后遍历左孩子，再遍历右孩子，但是要先在栈中放入右孩子，再放入左孩子。
- 中序遍历是要先遍历左孩子，之后遍历中间结点，再遍历右孩子。要找到最左边的孩子，就要深度优先可是进行搜索(root = root->left),之后访问中间结点。对访问的中间结点的右孩子也执行这个过程。
- 后序遍历看解析
- 层序遍历是要记录当前层有多少个结点，对这些结点进行遍历。
- 按之字形打印是交替打印的，要考虑好两层的打印方式