题目

给你二叉树的根节点 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

题解

@SuppressWarnings("unchecked")
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();

    BiConsumer<TreeNode, Integer> recursion = new BiConsumer<TreeNode, Integer>() {
        @Override
        public void accept(TreeNode node, Integer layer) {
            if (null == node) {
                return;
            }
            if (result.size() < layer + 1) {
                result.add(new LinkedList<>());
            }
            // 将数字加入对应层级
            // 根据层级奇偶性进行锯齿形变换
            if (layer % 2 == 0) {
                ((LinkedList) result.get(layer)).addLast(node.val);
            } else {
                ((LinkedList) result.get(layer)).addFirst(node.val);
            }
            // 遍历左树
            this.accept(node.left, layer + 1);
            // 遍历右樹
            this.accept(node.right, layer + 1);
        }
    };
    recursion.accept(root, 0);

    return result;
}