精选力扣500题第13题 LeetCode 102. 二叉树的层序遍历【c++详细题解】

痛定思痛。 2021-07-24 11:46 210阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：  
二叉树：\[3,9,20,null,null,15,7\],

3
     / \
      9  20
        /  \
       15   7

返回其层序遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

### 2、思路 ###

**(BFS)** O(n)  
我们从根节点开始按宽度优先的顺序遍历整棵树，每次先扩展左儿子，再扩展右儿子。

这样我们会：

1.  先扩展根节点；
2.  再依次扩展根节点的左右儿子，也就是从左到右扩展第二层节点；
3.  再依次从左到右扩展第三层节点；
4.  依次类推

然后在遍历过程中我们给每一层加一个结尾标记`NULL`,当我们访问到一层的结尾时，由于`BFS`的特点，我们刚好把下一层都加到了队列中。这个时候就可以给这层加上结尾标记`NULL`了,每次遍历到一层的结尾`NULL`时，就将这一层添加到结果中。

### 3、代码 ###

/** * 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>> printFromTopToBottom(TreeNode* root) { 
            vector<vector<int>>res;
            if(!root) return res;
            queue<TreeNode*>q;
            vector<int>level; //记录一层的节点
            q.push(root);
            q.push(NULL);// 一层的结尾标记
            while(q.size())
            { 
                auto t = q.front();
                q.pop();
                if(!t)
                { 
                    if(!level.size()) break;
                    res.push_back(level);
                    level.clear();
                    q.push(NULL);
                }
                else
                { 
                    level.push_back(t->val);
                    if(t->left) q.push(t->left);
                    if(t->right) q.push(t->right);
                }
            }
            return res;
        }
    };

**原题链接：**[33. 搜索旋转排序数组][33.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[33.]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/b82cdef0816842af94f6b86fefb70c1b.png