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

此题的核心是对与二叉树的运用，既然是训练，那我们解此题就不可以用投机取巧的形势解决。
1、分左右两条子树
2、分别为左右子树创建一个保存子节点的队列，然后从队列里去取下一个该用的节点。用完后从队列里去掉该节点，并将其左右节点存入队列后方
3、如果想控制到节点的左右子树，我们必须要先为其创建一个值为-1的节点，若为空是控制不到后续子树的。所以当运行结束后，我们需要清除这些值为-1的子树。可用递归实现



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
        TreeNode headTree = new TreeNode(-1);
        List<TreeNode> treeLeft = new ArrayList<>();
        List<TreeNode> treeRight = new ArrayList<>();
        TreeNode leftNode = new TreeNode(-1);
        TreeNode rightNode = new TreeNode(-1);
        treeLeft.add(leftNode);
        treeRight.add(rightNode);       
        for (int i = 0; i < cows.length; i++) {
            if (cows[i] == 0) {   
                addTree(treeLeft, cows[i]);
            } else {
                addTree(treeRight, cows[i]);
            }
        }
        leftNode = deleteNull(leftNode);
        rightNode = deleteNull(rightNode);
        
        headTree.left = leftNode;
        headTree.right = rightNode;     
        return headTree;
    }

    public static boolean addTree(List<TreeNode> treeList, int var) {
        if (treeList.get(0).val == -1) {
            TreeNode leftNode = new TreeNode(-1);
            TreeNode rightNode = new TreeNode(-1);
            treeList.get(0).val = var;         
            treeList.get(0).left = leftNode;
            treeList.get(0).right = rightNode;
            treeList.add(leftNode);
            treeList.add(rightNode);
            treeList.remove(0);
        } 
        return true;
    }

  // 删除值为-1的子树
    public static TreeNode deleteNull(TreeNode treeNode) {
        if (treeNode.val == -1) {
            return null;
        } else {
            treeNode.left = deleteNull(treeNode.left);
            treeNode.right = deleteNull(treeNode.right);
            return treeNode;
        }

    }
}