LeetCode: 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],
]

---

We can use the same code as Binary Tree Level Order Traversal. Just reverse the result at the end.

C++ Code:

/*
 * func: get_height
 * goal: get the height of the binary tree
 * @param root: root node of the tree
 * return: the height of the tree
 */
int get_height(TreeNode *root){
    if(root == nullptr){
        return 0;
    }else{
        int left_height = get_height(root->left);
        int right_height = get_height(root->right);
        
        return left_height > right_height ? left_height + 1 : right_height + 1;
    }
}

/*
 * func: traverse_given_level
 * goal: traverse the given level
 * @param root: root node of the tree
 * @param level: given level
 * @param routine: traversal list
 * return:
 */
void traverse_given_level(TreeNode *root, int level, vector<int> &routine){
    if(root == nullptr){
        return;
    }
    if(level == 1){
        routine.emplace_back(root->val);
    }else if(level > 1){
        traverse_given_level(root->left, level-1, routine);
        traverse_given_level(root->right, level-1, routine);
    }
}

/*
 * func: level_order_traversal_ii
 * goal: traverse the tree in level order from bottom up
 * @param root: root node of the tree
 * return: a vector of each level
 */
vector<vector<int> > level_order_traversal_ii(TreeNode *root){
    int level = get_height(root);
    vector<int> curr_level;
    vector<vector<int> > result;
    for(int i=level; i >= 1; --i){
        traverse_given_level(root, i, curr_level);
        result.emplace_back(curr_level);
        curr_level.clear();
    }
    return result;
}

Python Code:

# func: traverse the tree in level order from bottom up
# @param root: root node of the tree
# @return: a list of nodes in each level
def level_order_traversal_ii(root):
    if not root:
        return []
    result = []
    curr_level = [root]
    while curr_level:
        result.append([x.val for x in curr_level])
        next_level = []
        for node in curr_level:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        curr_level = next_level[:]

    return result[::-1]