[leetcode]. 107. Binary Tree Lev

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,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

解题思路：
本题和102. Binary Tree Level Order Traversal类似，只是遍历的时候102. Binary Tree Level Order Traversal是从上到下一层一层遍历，而本题是从下到上一层层遍历，基本思路相同，唯一的区别是要先求出二叉树的深度。

具体代码如下：

class Solution {
public:
    int getDepth(TreeNode* root)
    {
        if(!root) return 0;
        return max(getDepth(root->left), getDepth(root->right)) + 1;
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        int depth = getDepth(root);
        ret.resize(depth);
        int levelNumber = 0;
        queue<TreeNode*> level;
        level.push(root);
        
        while(!level.empty())
        {
            int size = level.size();
            for(int i = 0; i < size; ++i)
            {
                TreeNode* temp = level.front();
                level.pop();
                ret[depth - levelNumber - 1].push_back(temp->val);
                if(temp->left) level.push(temp->left);
                if(temp->right) level.push(temp->right);
            }
            levelNumber ++;
        }
        
        return ret;
    }
};