###### tags: `LeetCode` `Tree` `Recursion` `Medium`
# LeetCode #107 [Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/)
### (Medium)

給定一個二元樹，返回其節點值自底向上的層序遍歷。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）

---
最低葉節點的高度為0, 簡單的做法是將根節點設為0, 依照深度將子節點的數值插入對應數組位置, 最後再將整個數組反轉, 原本為最高高度的葉節點在反轉完後的高度變為0, 滿足題目要求。

要注意getDepth中的前兩行要先做, 否則會出現level大於ans.size()的overflow情況(但是增加ans大小的判斷是level==ans.size(), 也就是說, 當level大於ans.size()的時候不會滿足判斷式, 此時會發生overflow)。

---

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root)return ans;
        ans.emplace_back();
        ans[0].push_back(root->val);
        if(root->left)getDepth(root->left, 1);
        if(root->right)getDepth(root->right, 1);
        reverse(ans.begin(),ans.end());
        return ans;
    }
    void getDepth(TreeNode* node, int level){
        if(node){
            if(level==ans.size())ans.emplace_back();//先做
            ans[level].push_back(node->val);//先做
            if(node->left)getDepth(node->left, level+1);
            if(node->right)getDepth(node->right, level+1);
        }
    }
};