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

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

知识点:

树，双端队列

解题思路:

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

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

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

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