二叉树层次遍历

二叉树层次遍历，又称为宽度优先搜索，按树的层次依次访问树的结点。层次遍历使用队列对遍历节点进行 存储，先进入队列的结点， 优先遍历拓展其左孩子与
右孩子。

#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))
            }
        }
    }
};