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

import java.util.*;

/*
 * 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>> res = new ArrayList<>();
        if (root == null)
            return new int[0][0];

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);

        while (!s1.empty() || !s2.empty()) {
            int n = s1.size();
            TreeNode node = null;
            List<Integer> vec = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                node = s1.pop();
                vec.add(node.val);

                if (node.left != null)
                    s2.push(node.left);
                if (node.right != null)
                    s2.push(node.right);
            }

            if (vec.size() > 0)
                res.add(new ArrayList<>(vec));

            vec.clear();
            n = s2.size();

            for (int i = 0; i < n; i++) {
                node = s2.pop();
                vec.add(node.val);

                if (node.right != null)
                    s1.push(node.right);
                if (node.left != null)
                    s1.push(node.left);
            }

            if (vec.size() > 0)
                res.add(new ArrayList<>(vec));
        }

        int[][] result = new int[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            List<Integer> row = res.get(i);
            result[i] = new int[row.size()];
            for (int j = 0; j < row.size(); j++) {
                result[i][j] = row.get(j);
            }
        }

        return result;
    }
}

代码使用的编程语言是Java。

这道题目考察的是二叉树的层序遍历，要求按照Z字形的顺序输出每一层的节点值。

解决这个问题的思路是使用两个栈s1和s2来分别保存当前层和下一层的节点。首先将根节点入栈s1，并进入循环，直到s1和s2都为空为止。

在每一次循环中，首先判断当前s1栈是否为空，如果不为空，则将s1栈中的节点依次出栈，并将它们的值加入到一个临时列表vec中。同时，如果节点有左孩子，则将左孩子入栈s2；如果节点有右孩子，则将右孩子入栈s2。当s1栈为空时，将vec列表加入到结果列表res中。

清空vec列表，并判断当前s2栈是否为空，如果不为空，则将s2栈中的节点依次出栈，并将它们的值加入到vec列表中。同时，如果节点有右孩子，则将右孩子入栈s1；如果节点有左孩子，则将左孩子入栈s1。当s2栈为空时，将vec列表加入到结果列表res中。

将结果列表res转换为二维数组并返回。

代码通过两个栈的交替使用，实现了按照Z字形顺序遍历二叉树节点的要求。