LeetCode: Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

---

There are two ways to do level traversal. One is to compute the height of the tree first and then traverse each level by height recursively. The other way is to use a queue to contain nodes in current level and then push the nodes in the next level while popping nodes from current level.

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
 * goal: traverse the tree in level order
 * @param root: root node of the tree
 * return: a vector of each level
 */
vector<vector<int> > level_order_traversal(TreeNode *root){
    int level = get_height(root);
    vector<int> curr_level;
    vector<vector<int> > result;
    for(int i=1; i <= level; ++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
# @param root: root node of the tree
# @return: a list of nodes in each level
def level_order_traversal(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

Reference Link:

1. Level Order Tree Traversal | GeeksforGeeks: http://www.geeksforgeeks.org/level-order-tree-traversal/