Simple Java Solution With Explanation


  • 0

    For this problem I wanted to use as much of the standard "Level Order Traversal" Algorithm as possible. I went with the BFS level order algorithm with a slight modification. If we take a look at the zigzag property its nothing more than alternating which end of the temp list is being added to (either the front or the back). This is a simple spec to code for. I kept a variable level and before adding to a given levels list i check rather the level variable is odd or even. If Odd I add to the front of the list if even I add to the back.

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            
            List<List<Integer>> levels = new ArrayList<List<Integer>>();
            if(root == null) return levels;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            int level = 0;
            while(!q.isEmpty()){
                int size = q.size();
                List<Integer> list = new ArrayList<Integer>();
                for(int i = 0; i < size; i++){
                   TreeNode n = q.remove();
                   if(level % 2 == 1){
                       list.add(0,n.val);
                   }else{
                       list.add(n.val);
                   }
                   if(n.left != null) q.add(n.left);
                   if(n.right != null) q.add(n.right);
                }
                level++;
                levels.add(list);
            }
            return levels;
        }
    }

Log in to reply
 

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