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

考察知识点： 二叉树、队列、广度优先搜索

题目分析：

 题目的要求是将一段数组中的值按0和1分到二叉树上，例如：

 还要求是完全二叉树，可以根据层序遍历的思想，利用两个队列分别建立左右子树，左子树保存0，右子树保存1。队列中存储非空指针，对每一个新的数，尝试将其放入队列中首个结点的左孩子和右孩子，如果右孩子已经有值，将队列pop并获得队列中下一个结点重新操作即可。

所用编程语言： 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类
     */
    void insert(queue<TreeNode*> &cows, int cow, TreeNode *H)
    {
        if (cows.empty()) {
            if (cow == 0) {
                H->left = new TreeNode(cow);
                cows.push(H->left);
            } else {
                H->right = new TreeNode(cow);
                cows.push(H->right);
            }
        } else {
            TreeNode *p = cows.front();
            if (p->right) {
                cows.pop();
                p = cows.front();
            }
            if (!p->left) {
                p->left = new TreeNode(cow);
                cows.push(p->left);
            } else if (!p->right) {
                p->right = new TreeNode(cow);
                cows.push(p->right);
            }
        }
    }
    TreeNode* sortCowsTree(vector<int>& cows) {
        // write code here
        TreeNode *H = new TreeNode(-1);
        queue<TreeNode*> white;
        queue<TreeNode*> black;
        int size = cows.size();
        for (int i = 0; i < size; i++) {
            int cow = cows[i];
            if (cow == 0) insert(black, 0, H);
            else insert(white, 1, H);
        }
        return H;
    }
};