binary tree level order traversal II.

binary_tree_level_order_traversal_II.cpp

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * 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]
]

 */
class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        //two queue to hold parents and their children
        //  if parentQ is empty, one level is done; record all int at this levle
        //
        // Final, reverse order of vvInt 
        vector<vector<int> >vvInt;
        vector<int> vInt;
        queue<TreeNode *> parentQ;
        if (root)
            parentQ.push(root);
        queue<TreeNode *> childQ;
        while (!parentQ.empty()) {
            TreeNode *aNode = parentQ.front();
            parentQ.pop();
            vInt.push_back(aNode->val);
            if (aNode->left)
                childQ.push(aNode->left);
            if (aNode->right)
                childQ.push(aNode->right);
            
            if (parentQ.empty()) {
                swap(parentQ, childQ);
                vvInt.push_back(vInt);
                vInt.clear();
            }
        }
        //reverse the order of vvInt;
        int size = vvInt.size();
        int half = size/2;
        for(int i=0; i<half; i++)
            swap(vvInt[i], vvInt[size-1-i]);
        return vvInt;
    }
};