107

之前已經寫過level order traversal，一個偷懶的方法就是先做完level order traversal，再把最後得到的vector裡面的元素反向一下就好。

/**
 * 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) {
        vector<vector<int>> inverted_ans, ans;
        vector<TreeNode*> level_list, next_level_list;
        vector<int> val_vec;

        if(root == NULL)
            return ans;
        else
            level_list.push_back(root);

        while(level_list.size() != 0)
        {
            val_vec.clear();

            for(int i=0; i<level_list.size(); i++)
                val_vec.push_back(level_list[i]->val);

            inverted_ans.push_back(val_vec);


            next_level_list.clear();
            for(int i=0; i<level_list.size(); i++)
            {
                if(level_list[i]->left != NULL)
                    next_level_list.push_back(level_list[i]->left);
                if(level_list[i]->right != NULL)
                    next_level_list.push_back(level_list[i]->right);
            }
            level_list = next_level_list;
        }

        for(int i=inverted_ans.size()-1; i>=0; i--)
            ans.push_back(inverted_ans[i]);

        return ans;
    }
};

有需要的話再來想想怎麼寫出更適合用來解這題的版本。