学算法-二叉树的层次遍历

发表于 | 分类于 | 阅读数

最近做题在做BFS系列，找到了有关二叉树层次遍历的几道题

二叉树的层次遍历使用的方法就是使用的BFS的思想，如下面一道题：

二叉树的层序遍历

题意：
给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7]
1
层次遍历的结果：
[
[3],
[9,20],
[15,7]
]

分析

BFS就是利用队列逐层遍历的，只不过此时需要我们进行一个分层的操作，分层操作我采用的思想是：
用一个变量cnt记录每一层的数量，当该层元素从队列中弹出的时候，cnt–，当cnt变为0的时候，证明该层元素都已遍历完，我们在遍历的时候可以用一个临时的vector来存储，然后此时队列中存储的是下一层元素，将cnt更新为队列的尺寸，然后将临时vector存入ans中，清空该vector即可

代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        int cnt=0;
        queue<TreeNode *>q;
        vector<vector<int>> ans;
        if(!root)return ans;
        q.push(root);
        cnt=1;
        vector<int>temp;
        while(!q.empty()){
            TreeNode *tempNode=q.front();
            q.pop();cnt--;
            if(tempNode->left)q.push(tempNode->left);
            if(tempNode->right)q.push(tempNode->right);
            if(cnt>0){
                temp.push_back(tempNode->val);
            }else{
                temp.push_back(tempNode->val);
                cnt=q.size();
                ans.push_back(temp);
                temp.clear();
            }
        }
        return ans;
    }
};

二叉树的层次遍历II

题意：
相比于第一个做出的改变是“返回其节点值自底向上的层次遍历”
这个其实就是将遍历的每层结果插到最终结果的前面就可以了，解决倒序的问题
这个用vector.insert(vector.begin(),元素)即可解决
不放代码了

二叉树的锯齿形层次遍历

题意：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
如第一道例题里面的二叉树返回的结果为：
[
[3],
[20,9],
[15,7]
]
一种交替的效果
这个就需要根据正在遍历的层数的奇偶，而做出不同的操作，这里用到了c++中的双向队列deque<TreeNode *>dq
取前值:dq.front();;去前值:dq.pop_front();;插前值:dq.push_front(tempN->left);;
取后值:dq.back();;去后值:dq.pop_back();;插后值:dq.push_back(tempN->right);;
这题画图分析即可
重点关注奇偶层的插入是插在前面还是插在后面，取前面的值还是取后面的值
当然还有一种方法：层次遍历后，按偶数层倒置，不过这种麻烦一些

代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(root==NULL)return ans;
        deque<TreeNode *>dq;
        vector<int>temp;
        dq.push_back(root);
        int cengshu=1;
        int cnt=1;
        while(!dq.empty()){
            TreeNode *tempN;
            if(cengshu%2==0){
                tempN=dq.front();
                dq.pop_front();
                cnt--;
                if(tempN->right){
                    dq.push_back(tempN->right);
                }
                if(tempN->left){
                    dq.push_back(tempN->left);
                } 
            }else{
                tempN=dq.back();
                dq.pop_back();
                cnt--;
                if(tempN->left){
                    dq.push_front(tempN->left);
                }
                if(tempN->right){
                    dq.push_front(tempN->right);
                }
            }
            if(cnt>0){
                temp.push_back(tempN->val);
            }else{
                temp.push_back(tempN->val);
                cnt=dq.size();
                ans.push_back(temp);
                temp.clear();
                cengshu++;
            }
        }
    return ans;
    }
};