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

知识点

树，双端队列

解题思路

建立两颗树，left为左子树全部存放0的树，right为右子树全部存放1的。

以left举例，使用双端队列存放left树的全部节点。

当循环cows数组cow为0时，我们使用leftDeque，如果leftDeque为空，就直接添加个新树进去。

如果leftDeque不为空，从尾部也就是最早添加的节点取一个出来node，如果这个node的左子树为空，我们就把新的树添加到它的左子树上，再把新的树和node放回到队列中，新树放到leftDeque的头部，node再放回尾部；如果这个node左子树不为空，我们就把右子树设置为新的树，新的树放到leftDeque的头部。

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
        Deque<TreeNode> left = new ArrayDeque<>(); //左容器
        Deque<TreeNode> right = new ArrayDeque<>(); //右容器
        TreeNode zero = null; //左子树
        TreeNode one = null; //右子树
        Deque<TreeNode> temp; //左容器或者右容器
        for (int cow : cows) {
            temp = cow == 0 ? left : right;
            if(temp.isEmpty()){ //容器为空，添加第一颗树
                if(cow == 0) {
                    zero = new TreeNode(cow);
                    temp.offerFirst(zero);
                } else {
                    one = new TreeNode(cow);
                    temp.offerFirst(one);
                }
            } else {
                //从容器中取出最早添加的没有左子树或者右子树的树
                TreeNode treeNode = temp.pollLast(); 
                TreeNode newNode = new TreeNode(cow);
                if(treeNode.left == null){
                    //左子树还没满把新的节点添加到左子树上，并放回队列
                    treeNode.left = newNode;
                    temp.offerLast(treeNode);
                } else {
                    //左子树已满，添加到右子树，就不放回队列了
                    treeNode.right = newNode;
                }
                temp.offerFirst(newNode);
            }
        }
        TreeNode ans = new TreeNode(-1);
        ans.left = zero;
        ans.right = one;
        return ans;
    }
}