Standard java BFS solution


  • 0
    F
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            ArrayList<List<Integer>> result = new ArrayList<>();
            if (root == null) {
                return result;
            }
            int level = 0;
            Queue<TreeNode> queue = new ArrayDeque<>();
            result.add(Collections.singletonList(root.val));
            queue.offer(root);
            while (!queue.isEmpty()) {
                List<TreeNode> list = new ArrayList<>(queue);
                queue.clear();
                List<Integer> tmp = new ArrayList<>();
                for (TreeNode treeNode : list) {
                    TreeNode left = treeNode.left;
                    TreeNode right = treeNode.right;
                    if (left != null) {
                        tmp.add(left.val);
                        queue.offer(left);
                    }
                    if (right != null) {
                        tmp.add(right.val);
                        queue.offer(right);
                    }
                }
                if (++level % 2 != 0) {
                    Collections.reverse(tmp);
                }
                result.add(tmp);
            }
            result.remove(result.size() - 1);
            return result;
        }

Log in to reply
 

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