69. 二叉树的层次遍历层次遍历+queue

给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问) 样例 给一棵二叉树 {3,9,20,#,#,15,7}

  3
 / \
9  20
  /  \
 15   7

返回他的分层遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

层次遍历+queue

参见数据结构与算法中写的,层次遍历是需要借助queue来做的,单纯的逐层遍历写起来是比较简单的,像这样要求不同的层还要放在不同的vector中,稍微难一点,我一开始也没想好到底怎么做,参考了别人的代码,实际上也不是很难,主要是记录一下每层的长度,那如何知道每一层的长度呢,用了一个很巧妙的方法。

  1. 首先建立一个队列que,把根节点放进去。伪代码:
while(que非空)
{
        建立vector<int>   x;
        int len=que.size();
       while(len--)
      {
            把front->val放进x,并删掉front;
            把front的左右子节点放入que;(先把front节点记录下来)            
      }
      把x放入vecto<vector<int>>  res ;
} 
返回  res;

这样操作的巧妙之处在于每次可以用len记录当前层的节点的个数,然后通过while循环把当前节点的下一层放进queue,这样while出来之后刚好是遍历完了这一层(而且已经删掉),queue里面剩下的就是下一层的节点了。

vector<vector<int>> levelOrder(TreeNode * root) {
        vector<vector<int>>  res;
        if(!root)
        return res;
        
        queue<TreeNode*>   que;
        que.push(root);
        int len=1;      //第一个节点的大小
        
        while(!que.empty())
        {
            len=que.size();
            vector<int> vtmp;
            
            
            while(len--)
            {
                TreeNode *tmp;
                tmp=que.front();
                vtmp.push_back(tmp->val);
                que.pop();
                if(tmp->left)   que.push(tmp->left);
                if(tmp->right)  que.push(tmp->right);
                
            }
            if(!vtmp.empty())
                res.push_back(vtmp);
        }
        return res;
        
        // write your code here
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android知识点总结

03--图解数据结构之双链表实现容器

12650
来自专栏云霄雨霁

数据压缩----霍夫曼树和霍夫曼压缩

20400
来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

16020
来自专栏java思维导图

JAVA容器-自问自答学ArrayList

前言 这次我和大家一起学习HashMap,HashMap我们在工作中经常会使用,而且面试中也很频繁会问到,因为它里面蕴含着很多知识点,可以很好的考察个人基础。但...

37990
来自专栏计算机视觉与深度学习基础

Leetcode 282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all pos...

35660
来自专栏苦逼的码农

【链表问题】删除单链表中的第K个节点

如果 num > K, 则属于第三种情况,此时删除倒数第 K 个节点等价于删除第 (num - k + 1) 个节点。

27610
来自专栏C语言及其他语言

10个经典的C语言小程序

来源:codeceo 今天给大家分享10个比较基础的C语言的小程序,希望给C语言初学者带来一定帮助。 1、题目:有1、2、3、4个数字,能组成多少个互不相同且...

731130
来自专栏java小白

为什么hashMap的容量是2的幂次

59040
来自专栏LeetCode

2个线性表查找的优化

实际上,如果待查的数据比较均匀,那么1/2是一个很好的选择,一旦待查数据中的数据是极度不均匀的,那么就需要考虑插值查找法。

12840
来自专栏小文博客

小文’s blog–插入排序–《蓝桥杯代码笔记5》

17520

扫码关注云+社区

领取腾讯云代金券