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

知识点

完全二叉树 层序遍历

思路

题目要求统计0和1的数量，分别在根节点的左右子树建立完全二叉树，然后返回根节点。

我们遍历数组统计0和1的个数，之后利用层序遍历（BFS）的方法建立完全二叉树，并返回根节点作为答案的左右子树。具体见代码。

时间复杂度

由于只会建立n个节点并每个节点遍历一次，时间复杂度为

AC code （C++）

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector 
     * @return TreeNode类
     */
    TreeNode* sortCowsTree(vector<int>& cows) {
        vector<int> cnt(2);
        for (auto x : cows) {
            cnt[x] += 1;
        }
        TreeNode* root = new TreeNode(-1);
        root->left = get(cnt[0], 0);
        root->right = get(cnt[1], 1);
        return root;
    }
    TreeNode* get(int k, int val) {
        if (!k) return nullptr;
        auto res = new TreeNode(val);
        k --;
        queue<TreeNode*> q;
        q.push(res);
        while (k > 0) {
            if (k >= 2) {
                auto t = q.front();
                q.pop();
                t->left = new TreeNode(val);
                t->right = new TreeNode(val);
                k -= 2;
                q.push(t->left);
                q.push(t->right);
            }
            else {
                auto t = q.front();
                q.pop();
                t->left = new TreeNode(val);
                k -= 1;
                q.push(t->left);
            }
        }
        return res;
    }
};