层序遍历其实很简单，就是建立一个队列，然后把二叉搜索树的根节点放进去，对队列不为空进行循环，循环里依次把队列的头部拿出即可。
void levelOrder(){ queue<Node*>q; q.push(root);//使下面可以进入循环 while(!q.empty()){ //把头节点保存在一个临时变量里，以便后面循环 //必须要有不能用root,否则无法对左右子树的左右子树遍历 Node*node=q.front(); q.pop(); cout<<node->key<<endl; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } }上面因为有了队列，只要你插入队列是按照每一层的顺序进行，那出队列也一定是按每一层出去，所以可以进行层序遍历。
问题在于，题目要求出队列放在二维容器中，那么就必须要保证遍历的每一层的数保存在一个一维数组容器中。那应该怎样确定该数是同一层的呢？
在while循环中使用一个for循环，每一次循环的次数都是每一层的节点的个数。然后把这些节点插入到一维容器中去。 怎么保证每次的次数都是每层节点个数呢？每次循环结束，队列中新插入的数就是下一层节点的个数，看代码：
/** * 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>> levelOrder(TreeNode* root) { queue<TreeNode*> q; if(root!=NULL) q.push(root);//使下面可以进入循环 vector<vector<int>>v; while(!q.empty()){ int size = q.size(); vector<int>vec;//不能放在for循环里面，因为每一次while循环建立一个容器 //在for循环中每一次插入到队列的数量代表下一层的长度 //for中必须是size,不能是q.size,因为size保存的是上一轮的插入数量，代表这一层的长度，而q.size在循环中会因为插入而不断改变 for(int i=0;i<size;i++){ //要放在for循环里面，每次都产生一个新容器 TreeNode* Node = q.front();//没有这个不能下到每一层 q.pop(); vec.push_back(Node->val); if(Node->left) q.push(Node->left); if(Node->right) q.push(Node->right); } v.push_back(vec); } return v; } };仔细理解一下。
对于非二叉树，同样的思想，着重看一下而二叉树多个孩子的使用部分。
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector<vector<int>> levelOrder(Node* root) { queue<Node*> q; if(root!=NULL) q.push(root);//使下面可以进入循环 vector<vector<int>>v; //vector<int>result; while(!q.empty()){ int size = q.size(); vector<int>vec; for(int i=0;i<size;i++){ //要放在for循环里面，每次都产生一个新容器 Node* node = q.front();//没有这个不能下到每一层 q.pop(); vec.push_back(node->val); for(int i=0; i<node->children.size();i++){ if(node->children[i]) q.push(node->children[i]); } } v.push_back(vec); } return v; } };/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node* connect(Node* root) { queue<Node*> q; if(root!=NULL) q.push(root);//使下面可以进入循环 vector<vector<int>>v; while(!q.empty()){ int size = q.size(); vector<int>vec;//不能放在for循环里面，因为每一次while循环建立一个容器 //在for循环中每一次插入到队列的数量代表下一层的长度 //for中必须是size,不能是q.size,因为size保存的是上一轮的插入数量，代表这一层的长度，而q.size在循环中会因为插入而不断改变 Node* preNode; Node* node; for(int i=0;i<size;i++){ if(i==0){ preNode = q.front();//把每一层第一个节点取出来 q.pop(); node = preNode;//赋给node是为了往后继续插入左右子节点 }else{ node = q.front();//把头节点取出来 q.pop(); preNode->next = node;//先把前面保存的头节点指向下一个 preNode = node; //再把下一个节点作为头节点，以便下一次指向下下一个节点 } if(node->left) q.push(node->left); if(node->right) q.push(node->right); } preNode->next = NULL; //for循环结束后，把最后一个节点指向空 } return root; } };
层序遍历之一打7
然而竟然可以打十个！ 最amazing的一个是第是个如下： 给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3/ 9 20 / 15 7 返回它的最小深度 2.
/** * 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: int minDepth(TreeNode* root) { if(root==NULL)return 0; if(root->left==NULL && root->right==NULL) return 1; queue<TreeNode*>q; q.push(root); vector<vector<int>>v; while(!q.empty() ){ int size = q.size(); vector<int>vec; for(int i=0;i<size; i++){ TreeNode* node = q.front(); q.pop(); vec.push_back(node->val); if(node->left==NULL && node->right ==NULL) return v.size()+1; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } v.push_back(vec); } return v.size(); } };