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
        int[] cnt = new int[2];
        for (int x : cows) {
            cnt[x]++;
        }
        TreeNode root = new TreeNode(-1);
        root.left = get(cnt[0], 0);
        root.right = get(cnt[1], 1);
        return root;
    }

    private TreeNode get(int k, int val) {
        if (k == 0) return null;
        TreeNode res = new TreeNode(val);
        k--;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(res);
        while (k > 0) {
            if (k >= 2) {
                TreeNode t = q.poll();
                t.left = new TreeNode(val);
                t.right = new TreeNode(val);
                k -= 2;
                q.add(t.left);
                q.add(t.right);
            } else {
                TreeNode t = q.poll();
                t.left = new TreeNode(val);
                k -= 1;
                q.add(t.left);
            }
        }
        return res;
    }
}

该题考察的主要知识点有：

1. 二叉搜索树（Binary Search Tree，BST）：二叉搜索树是一种特殊类型的二叉树，其中每个节点的左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点。这种特性使得二叉搜索树可以方便地进行元素的查找和排序。
2. 中序遍历（Inorder Traversal）：中序遍历是二叉树遍历的一种方式，按照左子树、根节点、右子树的顺序访问节点。对于二叉搜索树来说，中序遍历会按照从小到大的顺序输出节点的值。
3. 队列（Queue）：队列是一种先进先出（First In First Out，FIFO）的数据结构。可以使用队列来辅助进行层序遍历或者其他需要按顺序处理的操作。

代码的解释大纲如下：

1. 创建一个根节点 root 并初始化为 -1。
2. 使用数组 cows 统计两种牛的数量，存储在数组 cnt 中。
3. 调用 get 函数，传入数量和相应的牛的编号，返回的节点作为根节点的左子树或右子树。
4. 在 get 函数中，如果数量 k 为 0，说明没有该种类的牛，返回 null。
5. 创建根节点 res，值为牛的编号。
6. 数量 k 自减 1。
7. 创建一个队列 q，将根节点 res 加入队列。
8. 当 k 大于 0 时，循环进行以下操作：如果 k 大于等于 2，表示还可以添加两个节点：弹出队列头部的节点，并为其创建左右子节点，值均为牛的编号。k 减 2。将左右子节点分别加入队列。否则，只能添加一个节点：弹出队列头部的节点，并为其创建左子节点，值为牛的编号。k 自减 1。将左子节点加入队列。
9. 返回根节点 res 作为结果。