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

题目考察的知识点

考察二叉树的深度优先搜索

题目解答方法的文字分析

需要统计0 1 的个数，随后利用队列从中取值，分别构建左右子树，将对应的值填入即可。

本题解析所用的编程语言

使用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--;
            }
        }
    }
}