Description

Submission

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root) return {};
        queue<pair<TreeNode*, int>> q;
        stack<pair<TreeNode*, int>> s;
        q.push(make_pair(root, 0));
        vector<vector<int>> res;
        vector<int> level {};
        int prevLevel = -1;
        while(!q.empty()) {
            auto p = q.front();
            TreeNode* r = p.first;
            int l = p.second;
            if(l != prevLevel && !level.empty()) {
                res.push_back(level);
                prevLevel = l;
                level.clear();
            }
            level.push_back(r->val);
            if(r->left) q.push(make_pair(r->left, l + 1));
            if(r->right) q.push(make_pair(r->right, l + 1));
            s.push(p);
            q.pop();
        }

        res.push_back(level);

        reverse(res.begin(), res.end());
        
        return res;
    }
};