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

和蔼的zhxing

发布于 2018-09-04 11:28:43

4480

发布于 2018-09-04 11:28:43

文章被收录于专栏：和蔼的张星的图像处理专栏

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）。

这是另外一个题的扩展，见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
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.02.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树