二叉树层次遍历，又称为宽度优先搜索，按树的层次依次访问树的结点。层次遍历使用队列对遍历节点进行 存储，先进入队列的结点， 优先遍历拓展其左孩子与
右孩子。
#include<queue>
#include<vector>
#include<stdio.h>
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x),left(NULL),right(NULL){}
};
void BFS_print(TreeNode *root ){
//宽度优先搜索二叉树
std:: queue<TreeNode *> Q;
Q.push(root);
while(!Q.empty()){
TreeNode *node = Q.front();
Q.pop();
printf("[%d]\n",node->val);
if(node->left){
Q.push(node->left);
}
if(node->right){
Q.push(node->right);
}
}
}
侧面观察二叉树
给定一个二叉树，假设从该二叉树的右侧观察它，将观察到的节点按照从上到下的顺序输出。
LeetCode 199. Binary Tree Right Side View
思考与分析
从二叉树的右侧观察它，将观察到的节点按照 从上到下的顺序输出，就是求 层次 遍历二叉树，每个层中的最后一个节点。
image.png
算法设计
使用Q层次遍历二叉树，遍历时，将 节点与层数绑定为pair，压入队列时，将节点 与层数同时压入队列，在 层次遍历中，每一层中的 最后一个节点最后遍历 到，随时更新每层的最后一个节点，存储到view数组中。
class Solution{
std::vector<int> rightSideView(TreeNode *root){
std::vector<int> view;//按层次遍历最后一个节点
std::queue<std::pair<TreeNode *, int>> Q;//<节点，层数>
if(root){
Q.push(std::make_pair(root,0));
}
while(!Q.empty()){
TreeNode * node = Q.front().first;//搜索节点
int depth = Q.front.second;
Q.pop();
if(view.size() == depth){
view.push_back(node->val);
}
else{
view[depth] = node->val;
}
if(node->left){
Q.push(std::make_pair(node->left,depth+1));
}
if(node->right){
Q.push(std::make_pair(node->right,depth + 1))
}
}
}
};
