70. 二叉树的层次遍历 II借助stack

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)。 原题见这里 这是另外一个题的扩展,见69题,这个题目要求层次遍历二叉树,并且把每一层放入一个vector,整体返回一个vector。 这个题要求是最底层的放在最前面。

借助stack

层次遍历是要借助queue的,这个不必多说,基本操作,怎么分层在69题中已经讨论过了,就是利用一个变量来计算每一层的容量。 然后每一层放入vector<vector<int>>中,这样放下来是顺序的,题目要求逆序,很容易想到的一种方法是借助stack,先进后出,我们都放入一个stack中,然后逐个取出来放入vector,虽然增加了一点空间消耗,但是复杂度并不高。 顺便看下stack的用法,c++primer中基本没有讲到stack,c++reference官网上可查:stack

几个主要的成员函数

作为LIFO(last in first out)容器,stack用的是非常多的,看这几个常用的成员函数也基本能理解,STL中stack也是作为模板类,所以其中存放的数据类型也是可以自定义的。

vector<vector<int>> levelOrderBottom(TreeNode * root) {
        vector<vector<int>> res;
        stack<vector<int>> sres;
        if(root==NULL)
        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())
            {
                sres.push(vtmp);          //放入堆栈
            }
            
        }
        while(!sres.empty())
        {                            //逐一出栈
            res.push_back(sres.top());
            sres.pop();
        }
        
        return res;
        
        // write your code here
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程微刊

从列表中或数组中随机抽取固定数量的元素组成新的数组或列表

2:jQuery版本 那么jQuery中怎么随机选出固定数组数组[1, 2, 3, 4, 5, 6, 7, 8, 9]中的三个元素,并构造成新数组的?

10910
来自专栏专注研发

交换排序—冒泡排序(Bubble Sort)

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们...

13120
来自专栏微信公众号:Java团长

Java 泛型详解

泛型是Java中一个非常重要的知识点,在Java集合类框架中泛型被广泛应用。本文我们将从零开始来看一下Java泛型的设计,将会涉及到通配符处理,以及让人苦恼的类...

12710
来自专栏灯塔大数据

技术 | Python从零开始系列连载(八)

导读 上一期学习了Python特色数据类型(列表)上半节,相信大家都已经熟悉啦,我们这一期就来学习Python特色数据类型(列表)下半节吧! 列表切片 列表切片...

37560
来自专栏CodeSheep的技术分享

Java编程思想学习录(连载之:一切都是对象)

17680
来自专栏卡少编程之旅

Javascript一些优雅实现

360110
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 四、数据结构:对象和数组

440100
来自专栏琦小虾的Binary

map 学习(下)——C++ 中的 hash_map, unordered_map

map 学习(下)——C++ 中的 hash_map, unordered_map 接上篇《map 学习(一)——C++中 map 的使用》。 一、hash_m...

3.7K70
来自专栏章鱼的慢慢技术路

斐波那契数列题型汇总

16760
来自专栏java工会

Java 泛型详解

20950

扫码关注云+社区

领取腾讯云代金券