leetcode刷题(剑指offer) 103.二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

解题思路与二叉树的层序遍历类似，我则是在遍历的基础上加了方向的标志位，依靠判断方向的标志位，对数组进行翻转。

代码如下：

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {if (null == root) {return new ArrayList<>();}Queue<TreeNode> queue = new ArrayDeque<>();TreeNode lastNode = root;TreeNode nextLastNode = null;// 0 表示从左往右， 1表示从右往左int direction = 0;List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();queue.add(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);nextLastNode = node.left;}if (node.right != null) {queue.add(node.right);nextLastNode = node.right;}if (node == lastNode) {lastNode = nextLastNode;if (direction == 1) {Collections.reverse(list);}res.add(list);list = new ArrayList<>();direction = 1 - direction;}}return res;}

但是这种方法是不是太笨了呢，明明可以直接存好，还特意进行了依次翻转逻辑，所以参考了大佬的代码。

直接遍历每一层的节点，然后根据当前是层级的奇偶，来对数组进行前向添加数据和后向添加数据，代码如下：

public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if (root != null) {queue.add(root);}while (!queue.isEmpty()) {LinkedList<Integer> list = new LinkedList<>();// queue里面是一层所有的节点for (int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();if (res.size() % 2 == 0) {list.addLast(node.val);} else {list.addFirst(node.val);}if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}res.add(list);}return res;}