题解 | #牛群的二叉树排序#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察了树的构建和遍历，队列的应用，以及对题目要求的理解和实现能力。

题目解答方法的文字分析

题目要求将牛按照指定规则排序，并构建一个满足条件的二叉树。根据题目描述，根节点的值为-1，0在左子树，1在右子树，并且左右子树都必须是完全二叉树。解决方法如下：

1. 统计数组中0和1的数量，分别记为 zeroNums 和 oneNums。
2. 创建根节点 res，值设为-1。
3. 调用 buildTree 函数分别构建左子树和右子树，传入对应的节点数和节点值。
4. 将左子树和右子树分别连接到根节点的左子节点和右子节点。
5. 返回根节点 res。

函数 buildTree 的步骤如下：

1. 如果节点数为0，返回空指针。
2. 创建根节点 root，值为传入的节点值 n。
3. 使用队列 layer 来逐层构建二叉树，首先将根节点入队。
4. 在循环中，每次取出队列首元素 s，如果还有未创建的节点，并且 s 的左子节点为空，就调用 createNodeAndEnqueue 函数创建一个值为 n 的左子节点，并将其入队。
5. 如果还有未创建的节点，并且 s 的右子节点为空，就调用 createNodeAndEnqueue 函数创建一个值为 n 的右子节点，并将其入队，同时将队列首元素出队列。
6. 继续循环直到所有节点都被创建完毕。
7. 返回根节点 root。

函数 createNodeAndEnqueue 的步骤如下：

1. 创建一个节点 node，值为传入的节点值 n。
2. 将节点 node 入队列。
3. 返回节点 node。

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cstddef>
#include <queue>
class Solution {
public:
    TreeNode* sortCowsTree(vector<int>& cows) {
        TreeNode* res = new TreeNode(-1); // 创建根节点，值为-1
        int zeroNums = 0;
        int oneNums = 0;
        
        // 统计数组中0和1的数量
        for (int i = 0; i < cows.size(); i++) {
            if (cows[i] == 0) {
                zeroNums++;
            } else {
                oneNums++;
            }
        }
        
        // 构建左子树和右子树
        TreeNode* l = buildTree(zeroNums, 0); // 0为左子树的值
        TreeNode* r = buildTree(oneNums, 1);  // 1为右子树的值
        
        res->left = l;
        res->right = r;
        
        return res;
    }

    // 构建满足要求的子树，nums为节点数目，n为节点的值
    TreeNode* buildTree(int nums, int n) {
        if (nums == 0) return NULL; // 如果节点数为0，返回空指针
        TreeNode* root = new TreeNode(n); // 创建根节点，值为n
        nums--;
        queue<TreeNode*> layer;
        layer.push(root);

        while (nums > 0) {
            TreeNode* s = layer.front(); // 取出队列首元素
            if (nums > 0 && s->left == NULL) {
                s->left = createNodeAndEnqueue(&layer, n, nums);
                nums--;
                continue;
            }

            if (nums > 0 && s->right == NULL) {
                s->right = createNodeAndEnqueue(&layer, n, nums);
                nums--;
                layer.pop(); // 当右子节点创建后，将首元素出队列
            }
        }
        
        return root;
    }

    // 创建节点并将节点入队列
    TreeNode* createNodeAndEnqueue(queue<TreeNode*>* layer, int n, int& nums) {
        TreeNode* node = new TreeNode(n); // 创建节点，值为n
        layer->push(node); // 入队列
        return node;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！