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;
}
