LeetCode刷题笔记 二叉树 层次遍历_二叉树层序遍历以数组形式输出

​ 通常使用广度优先搜索进行层次遍历。注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

102 二叉树的层序遍历

实现二叉树的层序遍历

输入一个二叉树，输出一个二维数组，表示二叉树层序遍历的结果

输入：[3,9,20,null,null,15,7]

 3
/ \
9  20
 /  \
15   7
1
2
3
4
5

输出：

[
[3],
[9,20],
[15,7]
]
1
2
3
4
5

解析：

​ 通常使用广度优先搜索进行层次遍历，使用一个队列存储当前层的所有节点。

​ 在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数。

​ 只要控制遍历这么多节点数，每遍历一个当前层的节点，将其出队列同时将其子节点入队列。

​ 通过这种操作就能保证每次遍历的队列中都是当前层的节点。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==nullptr){
            return res;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int queLen = que.size();
            vector<int> levelElem;
            for(int i=0;i<queLen;++i){
                auto node = que.front();
                que.pop();
                levelElem.push_back(node->val);
                if(node->left){
                    que.push(node->left);
                }
                if(node->right){
                    que.push(node->right);
                }
            }
            res.push_back(levelElem);
        }
        return res;
    }
};
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

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

给定二叉树的根节点 root ，返回其节点值的锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

输入是一个二叉树，输出是一个一维数组，表示二叉树的锯齿形层序遍历 。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

解析：

为了满足题目要求的返回值为（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）交替输出的锯齿形，我们可以利用双端队列 deque 的数据结构来维护当前层节点值输出的顺序。

双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个变量order记录是从左至右还是从右至左的：

• 如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。

• 如果从右至左，我们每次将被遍历到的元素插入至双端队列的头部。

除了使用双端队列，你也可以仅使用 vector，在需要从右至左的情况时反转临时数组中存储的该层结果。

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(!pRoot){
            return res;
        }
        bool order = true;
        queue<TreeNode*> queue;
        queue.push(pRoot);
        while(!queue.empty()){
            int len = queue.size();
            deque<int> level;
            for(int i=0;i<len;++i){
                auto node = queue.front();
                queue.pop();
                if(order){
                    level.push_back(node->val);
                }else{
                    level.push_front(node->val);
                }
                if(node->left){
                    queue.push(node->left);
                }
                if(node->right){
                    queue.push(node->right);
                }
            }
            order = !order;
            res.push_back(vector<int>(level.begin(),level.end()));
        }
        return res;
    }
};
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

637 二叉树的层平均值

给定一个二叉树，求每一层的节点值的平均数。

输入是一个二叉树，输出是一个一维数组，表示每层节点值的平均数。

输入：

3
/ \
9  20
/  \
15   7
1
2
3
4
5

输出：[3, 14.5, 11]
解释：第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

解析：

​ 使用一个先入先出的队列对二叉树进行层次遍历，遍历每一层的过程中累计该层的总和并在最后将平均值加入结果集。

​ 使用双层循环完成每层均值计算：外循环逐层遍历二叉树；内循环遍历队列中当前层的所有节点，计算当前层节点值均值，并将下一层节点压入队列。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        if(!root){
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int len = q.size();
            double sum = 0;
            for(int i=0;i<len;++i){
                auto node = q.front();
                q.pop();
                sum+=node->val;
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
            ans.push_back(sum/len);
        }
        return ans;
    }
};
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

513 找树左下角的值

给定一个二叉树，找出该二叉树的 最底层 最左边 节点的值

输入一个二叉树，输出一个整型值表示该二叉树左下角的值

输入: root = [2,1,3]
输出: 1

解析：

​ 本题很容易想到使用层次遍历解决，因为二叉树的 最底层 最左边 节点的值就是层次遍历最后一层的第一个节点值。

​ 所以，本题仅需要得到二叉树的层次遍历结果，然后将最后一层的第一个值返回即可。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans = 0;
        if(!root){
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int queLen = q.size(); // 要记录最初的队列长度，不然在后续push和pop操作中会影响该值
            ans = q.front()->val; // 记录当前层的第一个值
            for(int i=0;i<queLen;++i){
                auto node = q.front();
                q.pop();
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
        }
        return ans;
    }
};
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

参考资料

LeetCode 101：和你一起轻松刷题(C++) 第 14 章 指针三剑客之树