LeetCode107. 二叉树的层序遍历 II

先固定队列的大小，以此确定每层的个数，将出队元素入栈（先右孩子再左孩子），最后输出即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        stack<TreeNode*> st;    //存储输出节点
        deque<TreeNode*> queue; 
        vector<vector<int>> res;//存储最终结果
        vector<int> sizeOfEachLevel;    //存储每层节点个数

        if (root == NULL) return res;
        queue.push_back(root);
        /* 层次遍历，按照顺序将节点入栈，并记录每层节点个数 */
        while (!queue.empty())
        {   
            int size = queue.size();
            sizeOfEachLevel.push_back(size);
            for (int i = 0; i < size; i++)
            {
                TreeNode* cur = queue.front();
                queue.pop_front();
                st.push(cur);
                if (cur->right != NULL)
                    queue.push_back(cur->right);
                if (cur->left != NULL)
                    queue.push_back(cur->left);
            }
        }
        /* 输出 */
        /* 从最后一层倒序输出 */
        for (int i = sizeOfEachLevel.size() - 1; i >= 0; i--)
        {
            vector<int> curLevel;   //存储当前层结果
            int j = sizeOfEachLevel[i]; //当前层节点总数
            for (; j > 0; j--)
            {
                int top = st.top()->val;
                st.pop();
                curLevel.push_back(top);
            }
            res.push_back(curLevel);
        }
        return res;
    }
};