My easy to understand accepted JAVA solution


  • 0
    O

    My basic idea is to loop the tree level by level, and zigzag is achieved by alternately scanning the next level from left to right and from right to left. Super easy to understand:-) Time Complexity is O(N).

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> toReturn = new LinkedList<List<Integer>>();
            List<Integer> level = new LinkedList<Integer>();
    
            List<TreeNode> treeLevel = new LinkedList<TreeNode>();
            List<List<TreeNode>> treeLevels = new LinkedList<List<TreeNode>>();
    
            if(root == null){
                return toReturn;
            }
    
            //initializing first level
            int prelevelIndex = 0;
            treeLevel.add(root);
            level.add(root.val);
            treeLevels.add(prelevelIndex,treeLevel);
            toReturn.add(level);
    
            while(!treeLevel.isEmpty()){
                level = new LinkedList<Integer>();
                treeLevel = new LinkedList<TreeNode>();
                //loop through the previous level
                for (int i = treeLevels.get(prelevelIndex).size() - 1; i >= 0; i--) {
                    TreeNode t = treeLevels.get(prelevelIndex).get(i);
                    if (prelevelIndex % 2 == 0) { // scan the next level from right to left
                        if (t.right != null) {
                            level.add(t.right.val);
                            treeLevel.add(t.right);
                        }
                        if (t.left != null) {
                            level.add(t.left.val);
                            treeLevel.add(t.left);
                        }
                    } else { //zigzag is achieved by alternate scan the next level from left to right.
                        if (t.left != null) {
                            level.add(t.left.val);
                            treeLevel.add(t.left);
                        }
                        if (t.right != null) {
                            level.add(t.right.val);
                            treeLevel.add(t.right);
                        }
                    }
                }
                //initializing next level
                if(!treeLevel.isEmpty()){
                    prelevelIndex++;
                    treeLevels.add(prelevelIndex,treeLevel);
                    toReturn.add(level);
                }
            }
            return toReturn;
        }
    

Log in to reply
 

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