103. Binary Tree Zigzag Level Order Traversal

Description

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [3, 9, 20, null, null, 15, 7]

Output:

[

[3],

[20, 9],

[15, 7]

]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : O(N), where NN is the number of nodes in the tree.
 *    - We visit each node once and only once.
 *    - In addition, the insertion operation on either end of the deque takes 
 *        a constant time, rather than using the array/list data structure 
 *        where the inserting at the head could take the O(K) time 
 *        where K is the length of the list.
 * Space complexity : O(N) where NN is the number of nodes in the tree.
 *    - The main memory consumption of the algorithm is the queue that we use 
 *        for the loop, apart from the array that we use to keep the final output.
 */

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

Solution 2

/**
 * Time complexity : O(N), where N is the number of nodes in the tree.
 * Space complexity : O(H), where H is the height of the tree, i.e. the number 
 *    of levels in the tree, which would be roughly log2(N).
 */

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList();
        if(root == null) return resultList;
        helper(resultList, root, 0);
        return resultList;
    }
    
    private void helper(List<List<Integer>> resultList,
                       TreeNode node,
                       int level) {
        if(resultList.size() == level) {
            resultList.add(new ArrayList<Integer>());
        }
        
        if(level % 2 == 0) {
            resultList.get(level).add(node.val);
        } else {
            resultList.get(level).add(0, node.val);
        }
        
        if(node.left != null) {
            helper(resultList, node.left, level+1);
        }
        
        if(node.right != null) {
            helper(resultList, node.right, level+1);
        }             

    }
}

Follow up