Binary Tree Level Order Traversal II

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).

http://www.lintcode.com/en/problem/binary-tree-level-order-traversal-ii/

Discussion

在上一题的基础上调用reverse函数当然简单，但是作为上题的follow up，肯定不能这么简单。还有一个方法是先算出tree 的max depth。然后bottom-up level order traversal.

Solution

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode *> myque;
        vector<vector<int>> tmp;
        if(root == NULL) return tmp;
        myque.push(root);
        int max_depth = maxDepth(root);
        vector<vector<int>> result(max_depth);
        while (myque.empty() == false) {
           int n = myque.size();
            for(int i=0; i<n; i++) {
                TreeNode *tmp = myque.front();
                result[max_depth-1].emplace_back(tmp->val);
                myque.pop();
                if(tmp->left)
                    myque.push(tmp->left);
                if(tmp->right)
                    myque.push(tmp->right);
            }
            max_depth--;
        }
        //reverse(result.begin(), result.end());
        return result;
    }
    int maxDepth(TreeNode *root) {
        if(root == NULL) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) +1;
    }
};