学步园

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

思路：按层序遍历得到结果，然后逆序输出就ok了。

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int> >res;
        res.clear();
        if(root == NULL) {
            return res;
        }
        queue<TreeNode*> Q1;
        Q1.push(root);
        vector<int> a;
        while(!Q1.empty()) {
            queue<TreeNode*> Q2;
            a.clear();
            while(!Q1.empty()) {
                TreeNode* top = Q1.front();
                Q1.pop();
                if (top->left != NULL) {
                    Q2.push(top->left);
                }
                if (top->right != NULL) {
                    Q2.push(top->right);
                }
                a.push_back(top->val);
            }
            Q1 = Q2;
            res.push_back(a);
        }
        vector<vector<int> > rRes;
        int len = res.size();
        int i;
        for(i=len-1; i>=0; i--) {
            rRes.push_back(res[i]);
        }    
        return rRes;
    }
};