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

题目考察的知识点是：

本题主要考察二叉树的遍历。

题目解答方法的文字分析：

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

本题解析所用的编程语言：

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 zeros = 0;
        int ones = 0;
        for (int i : cows) {
            if (i == 0) {
                zeros++;
            } else {
                ones++;
            }
        }
        TreeNode root = new TreeNode(-1);
        if (zeros > 0) {
            TreeNode zero = new TreeNode(0);
            root.left = zero;
            sortCows(zero, zeros - 1, 0);
        }
        if (ones > 0) {
            TreeNode one = new TreeNode(1);
            root.right = one;
            sortCows(one, ones - 1, 1);
        }
        return root;
    }

    private void sortCows(TreeNode root, int num, int flag) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (num > 0) {
            TreeNode temp = queue.poll();
            TreeNode lTemp = new TreeNode(flag);
            temp.left = lTemp;
            queue.offer(lTemp);
            num--;
            if (num > 0) {
                TreeNode rTemp = new TreeNode(flag);
                temp.right = rTemp;
                queue.offer(rTemp);
                num--;
            }
        }
    }
}