题解 | #牛群Z字型排列#

import java.util.*;
import java.util.stream.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型二维数组
     */
    public int[][] ZLevelOrder (TreeNode root) {
        // write code here
        List<List<Integer>> ans = new ArrayList<>();
        levelOrder(root, 0, ans);
        return ans.stream().map(v -> v.stream().mapToInt(Integer::intValue).toArray())
                .collect(Collectors.toList())
                .toArray(new int[0][0]);
    }
    private void levelOrder(TreeNode root, int level, List<List<Integer>> ans) {
        if (root == null) return;
        if (level == ans.size()) ans.add(new ArrayList<>());
        if (level % 2 == 0) ans.get(level).add(root.val);
        else ans.get(level).add(0, root.val);
        levelOrder(root.left, level + 1, ans);
        levelOrder(root.right, level + 1, ans);
    }
}

• 基于二叉树的层序遍历实现，关键在于遍历到每一层时的特殊处理
• 若level层为偶数，则正常顺序添加元素到集合，即从List集合的尾部添加
• 若level层为奇数，则逆序添加，即每次从List集合的头部添加
• 也可以先做一遍层序遍历，得到层序遍历的结果；然后再在整理答案时，针对奇数层逆序。