Binary Tree Level Order Traversal II.txt

/**
 * Definition for binary tree
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> rets;
        if (root == NULL)
            return rets;
        list<TreeNode*>* inner = new list<TreeNode*>, *outer;
        inner->push_back(root);
        while(!inner->empty()) {
            outer = new list<TreeNode*>;
            rets.insert(rets.begin(), vector<int>(0));
            while(!inner->empty()) {
                TreeNode* node = inner->front();
                inner->pop_front();
                rets.front().push_back(node->val);
                if (node->left)
                    outer->push_back(node->left);
                if (node->right)
                    outer->push_back(node->right);
            }
            delete inner;
            inner = outer;
        }
        delete inner;
        return rets;   
    }
};