二叉树的锯齿形层序遍历 · 交互式算法学习

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {18        List<List<Integer>> ans = new ArrayList<>();19        if (root == null) {20            return ans;21        }22        Deque<TreeNode> q = new ArrayDeque<>();23        q.offer(root);24        boolean left = true;25        while (!q.isEmpty()) {26            List<Integer> t = new ArrayList<>();27            for (int n = q.size(); n > 0; --n) {28                TreeNode node = q.poll();29                t.add(node.val);30                if (node.left != null) {31                    q.offer(node.left);32                }33                if (node.right != null) {34                    q.offer(node.right);35                }36            }37            if (!left) {38                Collections.reverse(t);39            }40            ans.add(t);41            left = !left;42        }43        return ans;44    }45}