二叉树层次遍历

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



#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))
            }
        }
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 平时写代码没有时间限制,一笔试就各种手忙脚乱,昨天去哪儿笔试的时候也这样,写得乱七八糟的,二叉树遍历都能整出各种幺...
    假装会编程阅读 5,071评论 0 0
  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,509评论 1 31
  • 人总觉得,热闹在别处,而我什么也没有。 一个冷的人,老在寻找的人才会经常往热闹的地方去拥挤。 其实到最后你会发现,...
    村里灯花阅读 507评论 0 2
  • 今天安老师给我们留了一个有趣的作业,让我们回家找生活中的圆柱休和正方体还有球等等,这个作业太好了,我很喜欢...
    小王子WXN阅读 436评论 0 1