题解 | #牛群的二叉树排序#【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) {
        int[] count = new int[2];
        for (int i = 0; i < cows.length; i++) {
            count[cows[i]]++;
        }
        TreeNode root = new TreeNode(-1);
        root.left = get(count[0], 0);
        root.right = get(count[1], 1);
        return root;
    }

    private TreeNode get(int k, int val) {
	  // k==0表示已经没有可以分配的0或者1
        if (k == 0) return null;
	  // 分配一个值
        TreeNode res = new TreeNode(val);
	  // 数量-1
        k--;
	  // 队列用于存节点数据
        Queue<TreeNode> q = new LinkedList<>();
	  // 将res进行入队列，相当于初始化，放入根节点（非真根节点）
        q.offer(res);
        while (k > 0) {
		  // 如果k>=2,表示两个孩子都阔以被赋值
            if (k >= 2) {
			  // 出队列
                TreeNode t = q.poll();
			  // 给左右孩子分别赋值
                t.left = new TreeNode(val);
                t.right = new TreeNode(val);
			  // 数量-2
                k -= 2;
			  // 左右孩子分别入队列，因为他们仍然可能有子孩子，这就是递归向下
                q.offer(t.left);
                q.offer(t.right);
            } else {
			  // 如果k>0并且<2只有一种情况，k=1,只能分配一个结点的值
			  // 出队列
                TreeNode t = q.poll();
			  // 只能给左孩子赋值，因为数量不够
                t.left = new TreeNode(val);
			  // k--变为0
                k--;
			  // 其实可以去掉，因为下一次遍历k必然==0必然不能分配
                q.offer(t.left);
            }
        }
	  // 最后return的是左子树的根节点或者是右节点的根节点，也就是第二层的节点
        return res;
    }
}

本题知识点分析：

1.二叉搜索数

2.深度优先搜索

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

本题解题思路分析：

1.先计算0和1的数量

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

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

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

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

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

本题使用编程语言: Java

如果本题对您有帮助的话，可以点个赞支持一下，感谢~