###### tags: `leetcode`
# Question 107. Binary Tree Level Order Traversal II
### Description:
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).

### Solution:
- BFS + vector
- DFS:
- Find the deepest level
- recursively go to the current bottom
- get all the element of the current level
- go to the previous level
### AC code
code1, recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxD(TreeNode* root){
        if(root==NULL)
            return 0;
        else
            return (1+max(maxD(root->left), maxD(root->right)));
    }
    
    void level(TreeNode* root, int cur, int total, vector<int> &x){
        cout<<"cur: "<<cur<<", total: "<<total<<endl;
        if(root==NULL){
            cout<<"return"<<endl;
            return;            
        }
        cout<<"root->val: "<<root->val<<endl;
        if(cur==total){
            cout<<"push_back: "<<root->val<<endl;
            x.push_back(root->val);
        }
        else{
            cout<<"left: "<<endl;
            level(root->left, cur, total-1, x);
            cout<<"right: "<<endl;
            level(root->right, cur, total-1, x);
        }
    }
    
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        //get the max level
        int n = maxD(root);
        
        //return ans
        vector<vector<int>> ret;
        
        //start from level one
        int i = 1;
        while(i<=n){
            vector<int> cur;
            level(root, i, n, cur);
            ret.push_back(cur);
            i++;
        }
        return ret;
    }
};

code2, BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if(root==NULL)
            return ret;
        queue<TreeNode*>r;
        vector<int> cur;
        r.push(root);
        cur.push_back(root->val);
        ret.push_back(cur);
        TreeNode* tmp;
        while(!r.empty()){
            int n = r.size();
            vector<int> c;
            for(int i = 0 ; i < n ; i++){
                tmp = r.front();
                r.pop();
                if(tmp->left){
                    r.push(tmp->left);
                    c.push_back(tmp->left->val);
                }
                if(tmp->right){
                    r.push(tmp->right);
                    c.push_back(tmp->right->val);                    
                }
            }
            ret.push_back(c);
        }
        ret.pop_back();
        reverse(ret.begin(),ret.end());
        return ret;
    }
};