The title

Answer key

DFS algorithm breadth-first algorithm is used to expand the whole tree layer by layer. Each expanded layer of List is added from the right first, and the next layer is added from the left. List we use a two-end queue, offerLast() and offerFirst() at the next level. The complete code is as follows, which is also standard for DFS.

code

public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean isOrderLeft = true; while (! queue.isEmpty()) { int size = queue.size(); Deque<Integer> levelList = new LinkedList<>(); List<Integer> temp = new ArrayList<>(); for (int i = 0; i < size; ++i) { TreeNode curNode = queue.poll(); if (isOrderLeft) { levelList.offerLast(curNode.val); } else { levelList.offerFirst(curNode.val); } if (curNode.left ! = null) { queue.offer(curNode.left); } if (curNode.right ! = null) { queue.offer(curNode.right); } } ans.add(new ArrayList<>(levelList)); isOrderLeft = ! isOrderLeft; } return ans; }Copy the code

note

This article is participating in the “Nuggets 2021 Spring recruiting campaign”, click to see.