An easy understanding java solution based on level order traversal


  • 0
    S
    public class Solution {
        //add modification to levelorder traversel: for levels from left to right, add next node to the end of list
        //for levels from right to left, add next node to the front of the list
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new LinkedList<>();
            
            if(root == null)    return result;
            
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            
            boolean leftToRight = true;    //root level is left to right
            while(!q.isEmpty()){
                int size = q.size();
                List<Integer> list = new LinkedList<>();
                for(int i = 0; i < size; i++){
                    TreeNode node = q.poll();
                    if(leftToRight){
                        list.add(node.val);
                    }else{
                        list.add(0, node.val);
                    }
                    if(node.left != null)   q.offer(node.left);
                    if(node.right != null)  q.offer(node.right);
                   
                }
                
                result.add(list);
                leftToRight = !leftToRight;
            }
            
            return result;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.