二叉树-层序遍历
之前所述二叉树的递归遍历或者迭代遍历都属于深度优先搜索，即先迭代或者递归到树的某一枝最深处再逐渐回退，再到另一支的最深处再逐渐回退，从而完成遍历。而层序遍历属于广度优先遍历，即一层一层去遍历。
需要借助队列辅助实现一层一层遍历的逻辑，因为其先进先出的逻辑。而栈先进后出的逻辑适合模拟深度优先遍历即递归的逻辑。
层序遍历结果为：[[6] ,[4 7], [1 3 5 8]]
//队列辅助实现二叉树的层序遍历
class Solution{
public:
vector<vector<int>> levelOrder(TreeNode* root){
queue<TreeNode*> que;//生成一个队列，队列里的元素是树的节点指针
if(root!=NULL) que.push(root);
vector<vector<int>> result;//存放遍历结果
while(!que.empty()){
int size = que.size();//que.size()在后续不断变化
vector<int> vec;//存放当前层的遍历结果
for(int i = 0;i<size;i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.psuh(node->right);
}
result.push_back(vec);
}
return result;
}
};
//递归实现
//实现流程还是按照深度优先遍历的思维，随着递归进入左边的最深处，相应的建立对应的vector<int>,然后回退并不断将相应层的节点元素填入至对应的vector<int>中，与上述队列的广度优先搜索即从根节点开始一层一层遍历不同
class Solution{
public:
void order(TreeNode* cur,vector<vector<int>>& result,int depth){
if(cur==nullptr) return;
if(result.size()==depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left,result,depth+1);
order(cur->right,result,depth+1);
}
vector<vector<int>> levelorder(TreeNode* root){
vector<vector<int>> result;
int depth = 0;
order(root,result,depth);
return result;
}
}