https://leetcode.com/problems/binary-tree-level-order-traversal-ii/#/description

这题不难主要贴出使用vector和queue的两种算法(利用queue思路比较巧妙同时也比前者快)。

/**
 * 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>> vecResult;
        vector<vector<int>> res = coutVec0(root, 0, vecResult);
        reverse(res.begin(), res.end());
        return res;
    }
    vector<vector<int>> coutVec0(TreeNode* root,int level ,vector<vector<int>>& vecResult){
        if(!root){
            return vecResult;
        }
        
       if(level < vecResult.size()){
            //  vecResult[vecResult.size()-1-level].push_back(root->val);
            vecResult[level].push_back(root->val);
       }else if(level == vecResult.size()){
              vector<int> vec;
              vec.push_back(root->val);
            //   vecResult.insert(vecResult.begin(), vec);
            vecResult.push_back(vec);
        }
        ++level;
        coutVec0(root->left, level, vecResult);
        coutVec0(root->right, level, vecResult);
        return vecResult;
     }
};

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) {
        return res;
    }
    queue<TreeNode*> t;
    t.push(root);
    while (!t.empty()) { //将"某一层"的节点的子节点都放到队列中，并把原来的节点出列
        vector<int> tn;
        int cnt = t.size();
        for (unsigned int i = 0; i < cnt; ++i) {
            TreeNode *cur = t.front();
            tn.push_back(cur->val);
            t.pop();
            if (cur->left)
                    t.push(cur->left);
            if (cur->right)
                t.push(cur->right);
        }
        //do not use insert() here,it cost too much time.
        //use reverse() insteadly
        res.push_back(tn);
    }
    reverse(res.begin(), res.end());
    return res;
}