Share My Java Solution with One Queue


  • 1
    A
    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (root == null) {
                return result;
            }
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
            queue.add(root);
            int currentLevel = 1;
            int nextLevel = 0;
            boolean reversed = false;
            List<Integer> current = new ArrayList<Integer>();
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                current.add(node.val);
                currentLevel--;
                if (node.left != null) {
                    queue.add(node.left);
                    nextLevel++;
                }
                if (node.right != null) {
                    queue.add(node.right);
                    nextLevel++;
                }
                if (currentLevel == 0) {
                    if (reversed)
                        Collections.reverse(current);
                    result.add(new ArrayList<Integer>(current));
                    currentLevel = nextLevel;
                    nextLevel = 0;
                    current.clear();
                    reversed = !reversed;
                }
            }
            return result;
        }
    }
    

    Using a flag to indicate whether I should reverse or not, using two variables current and next to indicate where the line break happens.


Log in to reply
 

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