力扣HOT100(47) 二叉树的层序遍历

核心思路一句话讲透用队列来实现 “一层一层处理”先把根节点放进队列每次循环先记录当前队列里有多少个节点这就是当前层的节点数把这些节点一个一个取出来记录它们的值同时把它们的左右孩子如果有的话按顺序放进队列重复步骤 2-3直到队列为空。为什么用队列 因为队列是 ** 先进先出FIFO** 的结构正好符合 “先访问的节点它的孩子也先被访问” 的层序遍历要求。如果用栈后进先出就会变成深度优先遍历了。完整解题步骤初始化结果数组vectorvectorint ret用来存储每一层的节点值。边界处理如果根节点是空节点直接返回空的结果数组。初始化队列queueTreeNode* q把根节点root入队。外层循环处理每一层当队列不为空时记录当前队列的大小currentLevelSize这就是当前层的节点数往结果数组里添加一个空的一维数组用来存储当前层的节点值内层循环处理当前层的所有节点循环currentLevelSize次取出队首节点node把node-val添加到结果数组的最后一个一维数组里如果node有左孩子把左孩子入队如果node有右孩子把右孩子入队返回结果数组。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ret;//存最终的结果 if(root nullptr){ return ret; } //不为空的话就继续 //创建一个队 queue TreeNode* q; q.push(root); //进入循环 while(!q.empty()){ ret.push_back(vectorint()); int nums q.size();//每一层的个数 for(int i 0;inums;i){ TreeNode * nod q.front(); q.pop(); ret.back().push_back(nod-val); if(nod-left) q.push(nod-left); if(nod-right) q.push(nod-right); } } return ret; } };