LeetCode第 102 题：二叉树的层次遍历(C++)_leetcode 102 c++

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

BFS即可，借助队列。

此题的难点在于需要区分每一层的节点，所以我们入队的时候为每个节点都打上了标记（pair<TreeNode*, int>，第二位数字即为节点随身携带的标记），每一个节点对应的标记都是它的父节点的标记+1。

生成输出结果时方式其实很多，可以先一股脑全塞进vector里面，遍历结束再对vector细分即可，也可以选择使用哈希表进行维护（方便分类），不过我选择的是一边遍历一边生成结果，依据是节点的标记是否和上一个节点相同：

• 如果相同则继续加入辅助数组
• 如果不同，则将辅助数组先放入vec(结果数组)，并且将辅助数组清空

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vec; //结果数组
        vector<int> help; //辅助数组
        if(!root)   return vec;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        int flag = 0;
        while(!q.empty()){
            auto tmp = q.front();
            q.pop();  
            if(tmp.second != flag){
                vec.push_back(help);
                help.clear();
                flag = tmp.second;
            }
            help.push_back(tmp.first->val);

            if(tmp.first->left)
                q.push({tmp.first->left, tmp.second+1});
            if(tmp.first->right)
                q.push({tmp.first->right, tmp.second+1});
        }
        vec.push_back(help);
        return vec;
    }
};
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

一次处理多个的思路（很巧）
也可以通过记录队列的长度来进行每一层的判断：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vec; //结果数组
        if(!root)   return vec;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int len = q.size();
            vector<int> level;
            for(int i = 0; i < len; ++i){
                //就相当于一次处理q的size()个
                auto tmp = q.front();
                q.pop();  
                level.push_back(tmp->val);
                if(tmp->left)
                    q.push(tmp->left);
                if(tmp->right)
                    q.push(tmp->right);
            }
            vec.push_back(level);
        }
        return vec;
    }
};
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