题解 | #牛群的二叉树排序# 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 cows int整型一维数组
     * @return TreeNode类
     */
    public TreeNode sortCowsTree (int[] cows) {
        // write code here
        // 创建根节点并初始化为-1
        TreeNode root = new TreeNode(-1);

        // 使用两个队列分别存储当前层级的节点
        Queue<TreeNode> q0 = new LinkedList<>();
        Queue<TreeNode> q1 = new LinkedList<>();

        // 将根节点加入队列中
        q0.offer(root);
        q1.offer(root);

        // 遍历整数数组
        for (int i = 0; i < cows.length; ++i) {
            if (cows[i] == 0) {  // 如果当前值为0
                // 创建一个新节点，并将其作为当前层级节点的左子节点或右子节点（根据情况而定）
                TreeNode node = new TreeNode(0);
                if (q0.peek().left == null) {  // 如果当前层级节点的左子节点为空
                    q0.peek().left = node;  // 将新节点设置为左子节点
                    if (q0.peek() == root) {  // 如果当前层级节点是根节点
                        q0.poll();  // 从队列中移出
                    }
                } else {  // 如果当前层级节点的左子节点不为空
                    q0.peek().right = node;  // 将新节点设置为右子节点
                    q0.poll();  // 从队列中移出
                }
                q0.offer(node);  // 将新节点加入队列中
            } else {  // 如果当前值为1
                // 创建一个新节点，并将其作为当前层级节点的右子节点
                TreeNode node = new TreeNode(1);
                if (q1.peek() != root &&
                        q1.peek().left == null) {  // 如果当前层级节点不是根节点且左子节点为空
                    q1.peek().left = node;  // 将新节点设置为左子节点
                } else {  // 如果当前层级节点是根节点或者左子节点不为空
                    q1.peek().right = node;  // 将新节点设置为右子节点
                    q1.poll();  // 从队列中移出
                }
                q1.offer(node);  // 将新节点加入队列中
            }
        }

        // 返回根节点，即为转换后的二叉树
        return root;
    }
}

该Java代码使用Java编程语言编写。

该题考察的知识点是二叉树的构建和层次遍历。

这段代码实现了一个方法sortCowsTree，用于将给定的整数数组cows转换为二叉树。具体实现步骤如下：

1. 创建根节点root，初始值为-1，并且创建两个队列q0和q1，分别用于存储当前层级的节点。
2. 将根节点root加入队列q0和q1中。
3. 遍历整数数组cows，根据数组元素的值（0或1）来构建二叉树。
4. 若当前值为0，创建一个新节点，并将其作为当前层级节点的左子节点或右子节点。如果当前层级节点的左子节点为空，则将新节点设置为左子节点；否则，将新节点设置为右子节点。如果当前层级节点是根节点，则将其从队列q0中移出。最后，将新节点加入队列q0中。
5. 若当前值为1，创建一个新节点，并将其作为当前层级节点的右子节点。如果当前层级节点不是根节点且左子节点为空，则将新节点设置为左子节点；否则，将新节点设置为右子节点。如果当前层级节点是根节点或左子节点不为空，则将其从队列q1中移出。最后，将新节点加入队列q1中。
6. 完成整个数组的遍历后，返回根节点root，即为转换后的二叉树。

这段代码使用两个队列来分别存储当前层级的节点，通过队列的特性实现了层次遍历的效果。根据数组元素的值，逐个创建节点，并将节点连接到相应的位置上，最终构建出二叉树。