LeetCode: Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

---

We can use the same idea as level order traversal, just reverse the traversal list when current level is even.

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: zigzag_level_order
 * goal: traverse the tree in zigzag level order
 * @param root: root node of the tree
 * return: a vector of each level
 */
vector<vector<int> > zigzag_level_order(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);
        if(i & 1)
            result.emplace_back(curr_level);
        else{
            reverse(curr_level.begin(), curr_level.end());
            result.emplace_back(curr_level);
        }
        curr_level.clear();
    }
    return result;
}

Python Code:

# func: traverse tree in zig zag level order
# @param root: root node of the tree
# @return: a list of nodes in level order
def zigzag_level_order(root):
    if not root:
        return []
    result = []
    curr_level = [root]
    level = 1
    while curr_level:
        if level & 1 == 0:
            result.append([x.val for x in curr_level[::-1]])
        else:
            result.append([x.val for x in 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[:]
        level += 1

    return result