2ms Java Accepted Solution (Iterative) - easy to understand


  • 0
    D

    Basically do the level order traversal like the previous question, but for the alternating ones, do something like add(0, TreeNode.val) every time you add them to the list.

    '''
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> solution = new ArrayList<>();
        if (root == null) {
            return solution;
        }
    
        Queue<TreeNode> levelQ = new LinkedList<>(); // do a level order travesal
        levelQ.add(root);
        
        int lvl = 0;
        while (!levelQ.isEmpty()) {
            int numInLevel = levelQ.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < numInLevel; i++) {
                TreeNode curr = levelQ.poll();
                if (lvl % 2 == 0) {
                    level.add(curr.val);
                }
                else {
                    level.add(0, curr.val); // add in the front;
                }
                if (curr.left != null) {
                    levelQ.add(curr.left);
                }
                if (curr.right != null) {
                    levelQ.add(curr.right);
                }
            }
            solution.add(level);
            lvl++; // for alternating ones
        }
        return solution;   
    }
    

    '''


Log in to reply
 

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