LC103. Binary Tree Zigzag Level Order Traversal

Problem Description#

Source: https://leetcode.com/problems/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, null, null, 15, 7],

return its zigzag level order traversal as: [[3], [20, 9], [15, 7]].

Solution#

High level strategy#

Our strategy to solve this problem will be to conduct a breadth-first search. However, unlike an ordinary breadth-first search, we will only traverse from the left to right on even levels (including zero), and from the right to left on odd levels. The time complexity of this solution is O(n), where 'n' is equal to the number of nodes. The space complexity of this solution is O(logn), or O(h), where 'h' is equal to the height of the tree.

    3   level 0; traverse from left to right [3]
   / \
  9  20   level 1; traverse from right to left [20, 9]
    /  \
   15   7   level 2; traverse from left to right [15, 7]

Code#

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 **/

const zigzagLevelOrder = (root) => {
    let result = [];
    
    let recurse = (node, level) => {
        if (node === null) return;
        if (!result[level]) {
            result[level] = [];
        }
        
        if (level % 2 === 0) {
            result[level].push(node.val); // left to right traversal is implemented with the push method
        } else {
            result[level].unshift(node.val); // right to left traversal is implemented with the unshift method
        }
        
        recurse(node.left, level + 1);
        recurse(node.right, level + 1);
    };
    
    
    recurse(root, 0);
    return result;
};

Other Solutions#

We can potentially use a deque, insert it at head for odd levels, and tail for even levels

Java
Python

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> toRet = new ArrayList<>();
            if (root == null) return toRet;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int count;
            boolean leftToRight = true;
            while(!queue.isEmpty()){
                count = queue.size();
                ArrayList<Integer> level = new ArrayList<>();
                for (int i = 0; i < count; i ++){
                    TreeNode node = queue.poll();
                    if(leftToRight) {
                        level.add(node.val);
                    } else {
                        level.add(0, node.val);
                    }
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }
                }
                leftToRight = !leftToRight;
                toRet.add(level);
            }
            return toRet;
        }
}