[leetcode] 107: Binary Tree Level Order Traversal II (done)

/*

http://leetcode.com/onlinejudge#question_107

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

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:
    typedef vector<int> level_t;
    typedef vector<level_t> traversal_t;

    int depth(TreeNode * n)
    {
        if(!n) { return 0;}
        return std::max(depth(n->left), depth(n->right)) + 1;
    }
    traversal_t levelOrderBottom(TreeNode *root) {

        const int D = depth(root);
        traversal_t ret(D);
        for(int level = D-1; level >= 0; --level)
        {
            traverse(root, 0, level, ret);
        }
        return ret;
    }
    void traverse(TreeNode * n, int cur_level, int ret_level, traversal_t & ret)
    {
        if(!n) { return; }

        if(cur_level < ret_level)
        {
            traverse(n->left, cur_level+1, ret_level, ret);
            traverse(n->right, cur_level+1, ret_level, ret);
        }
        else if(cur_level == ret_level)
        {
            const int depth = ret.size();
            ret[depth - 1 - cur_level].push_back(n->val);
        }
    }
};