``` Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] 难度：medium 题目：给定二叉树，返回其之字型层次遍历结点值。 思路：层次遍历 Runtime: 1 ms, faster than 90.32% of Java online submissions for Binary Tree Zigzag Level Order Traversal.Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Binary Tree Zigzag Level Order Traversal. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (null == root) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int currentLevelCount = 1, nextLevelCount = 0; boolean direction = true; while (!queue.isEmpty()) { List<Integer> curLevelElems = new ArrayList<>(currentLevelCount); for (int i = 0; i < currentLevelCount; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.add(node.left); nextLevelCount++; } if (node.right != null) { queue.add(node.right); nextLevelCount++; } if (direction) { curLevelElems.add(node.val); } else { curLevelElems.add(0, node.val); } } result.add(curLevelElems); currentLevelCount = nextLevelCount; nextLevelCount = 0; direction = !direction; } return result; } } ```