LeetCode107—Binary Tree Level Order Traversal II

冷不防 2022-07-29 09:14 15阅读 0赞

# LeetCode107—Binary Tree Level Order Traversal II #

根据前/后序+中序遍历曾经考试常考，然而代码没写过，真是十分无奈。。等过两天学习了再来写  
这题是二叉树层序遍历。

--------------------

## 原题 ##

> Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
> 
> For example:  
> Given binary tree \{3,9,20,\#,\#,15,7\},  
> 　　　　3  
> 　　　/　　\\  
> 　　9　　　20  
> 　　　　　/　　\\  
> 　　　　15　　　7  
> return its bottom-up level order traversal as:  
> \[  
> \[15,7\],  
> \[9,20\],  
> \[3\]  
> \]

--------------------

## 分析 ##

层序遍历啊，然后把容器逆置，最简单直观的办法，至于还有没有更好的方法，等知道再写吧…

--------------------

## 代码 ##

class Solution {
    private:
        void help(vector<vector<int>>&result,TreeNode * root)
        {
            if(root == NULL)
                return;
            vector<TreeNode*> q;
            vector<int>tmp;
            int front = 0;
            int rear =1;
            q.push_back(root);
            while(front < q.size())
            {
                rear=q.size();
                while(front < rear)
                {
                    tmp.push_back(q[front]->val);
                    if(q[front]->left !=NULL)
                        q.push_back(q[front]->left);
                    if(q[front]->right !=NULL)
                        q.push_back(q[front]->right);
                    ++front;
                }
                result.push_back(tmp);
                tmp.clear();
            }
        }
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int>>result;
            help(result,root);
            vector<vector<int>>inverse(result.rbegin(),result.rend());
            return inverse;
        }
    };