力扣102 二叉树的层序遍历 广度优先搜索

二叉树的层序遍历

题目描述

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

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

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

解题思路

实现目标

• 将二叉树按照层数进行分类，并且将每一层的结点数据放到同一个数组，最后再用一个大数组将这些代表不同层数的数组包起来，也就是说最后需要返回一个二维数组。

用到的数据结构

• 队列：使用队列存放二叉树的结点，并且通过队列的大小来标记结点所在的层数。

核心思路—广度优先遍历

1. 先把根结点放到队列中，此时队列的大小为1，使用一个变量size来记录此时队列的大小。size的值即就是现在队列中存放结点在二叉树中的层数。
2. 创建一个一维数组来存放该层级的二叉树结点（本题中我用到了vector容器），怎么存放呢？什么时候存？------遍历size次，每一次都将队列的队首元素存入到一维数组中，同时如果队首元素有左右孩子，将队首元素的孩子们加入到队列的队尾，然后将队首元素弹出。
3. size次遍历完之后，此时意味着二叉树的一层遍历结束，此时需要将2中的一维数组加入到需要返回的二维数组中。
4. 循环2过程，直到队列为空。
5. 返回二维数组。

特殊情况

• 如果根结点本身就为空，直接返回一个空的二维数组即可。

代码

 vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> answer;//特殊情况if(!root){return answer;}queue<TreeNode*> q;//创建一个队列q.push(root);//将根结点放入队列中while(!q.empty()){int size = q.size(); vector<int> LevelNodes;//创建一个一维数组来存放该层级的所有结点//遍历size次for(int i =1;i<=size;i++){//将队首元素的值存放到一维数组中LevelNodes.push_back(q.front()->val);//如果左孩子存在，加入到队列尾部if(q.front()->left){q.push(q.front()->left);}//如果右孩子存在，加入到队列尾部if(q.front()->right){q.push(q.front()->right);}//弹出队首元素q.pop();}//将一位数组加入到要返回的二维数组中answer.push_back(LevelNodes);}return answer;}

通过