给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
在线做题地址→
样例 1: 输入:{1,2,3} 输出:[[1],[3,2]] 解释: 1 / \ 2 3 它将被序列化为 {1,2,3}
样例 2: 输入:{3,9,20,#,#,15,7} 输出:[[3],[20,9],[15,7]] 解释: 3 / \ 9 20 / \ 15 7 它将被序列化为 {3,9,20,#,#,15,7}
[题解]
算法：树的层次遍历
层次遍历，可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历，开辟一个新队列，让头结点入队并计算此时的长度，每次都将当前层的子节点全部压入队列，然后对下一层的节点进行遍历，再将下一层的子节点压入队列，不断循环，一直遍历到底层，判断的终止条件就是队列不为空。 循环里面，队列头出队，判断其是否有左右子结点，如果有，则将此点的子节点入队，但此时还不需要更新队列的长度，当前队列的长度是每层的长度。当这层的长度减为 0 时，就说明这层的遍历结束，开始更新长度为下一层的长度。 出队的元素的值按照一层层压入结果数组 因为题目锯齿形遍历 我们用一个 isforward 标记当前方向，每遍历完一层，如果是反向的，则将这层的节点数组倒序，然后将这层的集合压入结果
复杂度分析
时间复杂度 O(n)
n 为节点数量
空间复杂度 O(n)
存下所有点的信息 n 为节点数量 public class Solution { /** * @param root: A Tree * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values. */ public List<List<Integer>> zigzagLevelOrder(TreeNode root){ List<List<Integer>> ans = new ArrayList<List<Integer>>(); if (root == null) { return ans; } Queue<TreeNode> q = new LinkedList<TreeNode>(); //正反向标志 boolean isForward = true; q.offer(root); while (!q.isEmpty()) { int size = q.size(); List<Integer> subList = new ArrayList<Integer>(); for (int i = 0 ; i < size ; i++) { TreeNode treeNode = q.poll(); subList.add(treeNode.val); if (treeNode.left != null) { q.offer(treeNode.left); } if (treeNode.right != null) { q.offer(treeNode.right); } } //根据标志来确认当前层遍历的方向 if (!isForward) { Collections.reverse(subList);//翻转 } ans.add(subList); //方向反转 isForward = !isForward; } return ans; } }
更多题解参见