关于二叉树的层序遍历方式

发表于 更新于

心态崩了

蓝桥杯的题好难……前面几道填空题，暴力固然可以做，可是代码量大，能保证代码写出来不出错也是很难的……而有一些题目，要进行剪枝等等操作，还有一些题目，思路都很难想……虽然看了别人的的答案之后——啊呀！不就是这么一回事么！

可是自己做起来就是很难搞。

后面的几道大题就更是很难很难了。

线段树、前后缀和、图论……不是我吹，吹牛可以，真写起来是一道也不会。能写个dfs就已经快到极限了，用个滚动数组、滑动窗口、二分查找优化一下就是真的极限了……

今年的蓝桥杯能给我来一道比较简单的动态规划，我就真的谢天谢地。

马上又要开学了。感觉一个寒假过去啥也没学到，啥也不是…………下个学期课还算是比较少……但是有大学物理…………先走一步看一步吧，慢慢学，慢慢努力……蓝桥杯这种玩意……今年拿不了奖还可以明年再试试，然后到大三就努力备战考研了。

下面是代码部分

先来说说 queue

queue和栈最大的区别是queue是先进先出的，叫做队列，栈是先进后出的，类似于一个十分窄的箱子，前面放进去的东西就只好最后才能取出来。

队列则是类似于平时的排队，先排队的人先出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{
//C++队列Queue类成员函数如下:

back()//返回最后一个元素

empty()//如果队列空则返回真

front()//返回第一个元素

pop()//删除第一个元素

push()//在末尾加入一个元素

size()//返回队列中元素的个数

}

知道了queue的性质，来讲讲二叉树的层序遍历。

所谓的层序遍历就是把二叉树的每一层的元素都遍历出来，默认是从左到右，顺序是每一层，从根节点逐层向下。

那么输出的状态就是[[],[]]这样的，因为有的节点是有两个值的。或者不用这样只是输出排序也成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//在蓝桥杯里，不像是leetcode那样一切都是封装好，只需要写一个函数即可，在蓝桥杯上，要写一个完整的函数。
//首先导库
#include <bits/stdc++.h>  
using namespace std;
//我固然知道using namespace std是一种十分不好的行为，但是在蓝桥杯里本来也用不上太多的命名，一个using就可以解决一切问题。
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode (int x):val(x),left(nullptr),right(nullptr){}
};

//root = [3,9,20,null,null,15,7]  

vector<vector<int>> level(TreeNode* root){
    vector<vector<int>> res;//使用一个二维容器来储存数据。
    if(!root){
        return res;
    }
    //如果根节点是空的那就直接返回，下面的写法也可以实现同样的效果。
    /*
    if(root ==  nullptr)
        return res;
    */

    queue<TreeNode*> q;//创建一个队列用来层序遍历
    q.push(root);//先是将根节点入队。
    while(!q.empty()){//如果当前节点不为空
        int cursize = q.size();
        res.push_back(vector<int>());//往答案里添加一个容器。

        for(int i = 1;i<= cursize;i++){
            auto node = q.front();//node就是当前层的最左边的节点。
            q.pop();//删除队列中的第一个元素，注意，这个时候第一个元素已经被存到node里面了
            res.back().push_back(node->val);//向res的最后的vector存入node的值。注意这个时候node是第一个元素。然后将node所有的左右的元素也存进去。
            //然后继续向左右添加节点。
            if(node->left) 
                q.push(node->left);
            if(node->right)
                q.push(node->right);
        }
    }

    return res;

}

int main(void){
    TreeNode* root = new TreeNode(1);  
    root->left = new TreeNode(2);  
    root->right = new TreeNode(3);  
    root->right->left = new TreeNode(4);  
    root->right->right = new TreeNode(5); 
    vector<vector<int>>ans;
    ans = level(root);
    //在leetcode中此时直接return就可以结束了。
    int n = ans.size();
    for(int i = 0;i < n; i++)
    {
        int m = ans[i].size();
        for(int j = 0;j < m;j++)
        {
            cout<<ans[i][j];
            cout<<endl;
        }
    }
}

有几点是特别妙的。

首先就是使用队列可以减少空间开支，这样除了那些用来维护的内存、树本身的内存外只需要两层树的内存即可。
每一层都是root->left然后再root->right，这样本身就可以维护队列的从左到右。由于根节点只有一个，所以根节点无所谓是从左到右还是从右到左，其他的节点都是先左再右，然后再加上队列的先进先出的特点，这下子就可以实现从左到右的排列。

说说一个朴素的做法，也就是leetcode题解中提到的那一个做法，也是类似的历遍，但是是使用哈希表，使用一个二元组记录下节点与其对应的层数，使用哈希表来储存这些数据。

然后输出的时候就可以使用层数作为key来输出每一层的元素了。

那么锯齿层序遍历是怎么搞呢？锯齿层序遍历就是每一层遍历的顺序是反过来的，这一层是从左到右，下一层就是从右到左。

可以在存数据进res的时候反转一下数据、或者是需要翻转的时候就把此节点的值添加到队列的尾部，同样是从左到右遍历，那么添加的时候就已经从右到左添加了。

-我的Bilibili墨泽moozy

-我的公众号墨泽moozy

-我的知乎干干净净我的心

-我的博客