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

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

本题知识点分析：

1.二叉搜索数

2.深度优先搜索

3.队列存取（offer,add,remove,poll,element,peek,注意这些方法的区别（返回值问题））

本题解题思路分析：

1.先计算0和1的数量

2.创建值为-1的根节点

3.DFS分别创建左子树和右字树

4.注释很详细的解释了每一行的意义

5.其实就是分类讨论的情况

6.最后返回-1的根节点就可以了

本题使用编程语言: Java