LeetCode ---- 103、二叉树的锯齿形层次遍历

题目链接

思路：

利用102题二叉树的层次遍历的思路来解这道题

在102题解的基础上，使用一个boolean类型的变量来控制每次应该从左向右输出还是从右向左输出

初试时，从左向右输出，每遍历一层，方向变化一次

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root == null) {return ans;}// 开始时，应从左向右boolean left2Right = true;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {// 每一层节点总数int curLevelSize = queue.size();LinkedList<Integer> curLevel = new LinkedList<>();while (curLevelSize > 0) {TreeNode cur = queue.poll();curLevel.addLast(cur.val);if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}curLevelSize--;}// 从左向右if (left2Right) {ans.add(curLevel);} else {   // 从右向左List<Integer> reverseCurLevel = new LinkedList<>();while (!curLevel.isEmpty()) {   // 逆序添加进当前结果reverseCurLevel.add(curLevel.pollLast());}ans.add(reverseCurLevel);}left2Right = !left2Right;}return ans;}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}