Leetcode - 103. 二叉树的锯齿形层次遍历
解题思路参考代码中的注释：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 先进行层序遍历，然后再对奇数层（层数从0开始算）进行反转即可
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> layers = levelOrder(root);
// 对下标为奇数的List集合进行反转
for (int i = 1; i < layers.size(); i += 2) {
Collections.reverse(layers.get(i));
}
return layers;
}
// 上一题（https://leetcode-cn.com/problems/binary-tree-level-order-traversal/）的代码
private static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if (root == null) {
return ret;
}
// root节点单独作为第一层
LinkedList<TreeNode> layer = new LinkedList<>();
layer.add(root);
// 如果当前层还有节点
while (!layer.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = layer.size();
while (size-- > 0) {
TreeNode node = layer.pollFirst();
// 将当前层节点的信息存储下来
list.add(node.val);
// 添加下一层的节点
if (node.left != null) {
layer.add(node.left);
}
if (node.right != null) {
layer.add(node.right);
}
}
ret.add(list);
}
return ret;
}
}
