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

1. 题目考察的知识点 完全二叉树的定义，层次遍历

2. 题目解答方法的文字分析

   如果二叉树的深度为k，则除第k层外其余所有层节点的度都为2，且叶子节点从左到右依次存在。也即是，将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。

   首先统计cows数组中0和1的个数count，然后建立值为-1的头节点head。然后，调dfs(count,0)方法创建个数为count，节点值皆为0的完全二叉树，赋值给head的左子树。head的右子树同理。

   dfs方法讲解：运用层次遍历，创建完全二叉树，将所有没有左右子树的节点放进队列中，节点出栈时将，分别为节点加上左右节点。直到count为0

3. 本题解析所用的编程语言: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
        int[] cnt = new int[2];
        for (int x : cows) {
            cnt[x]++;
        }
        TreeNode root = new TreeNode(-1);
        root.left = get(cnt[0], 0);
        root.right = get(cnt[1], 1);
        return root;
    }

    private TreeNode get(int k, int val) {
        if (k == 0) return null;
        TreeNode res = new TreeNode(val);
        k--;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(res);
        while (k > 0) {
            if (k >= 2) {
                TreeNode t = q.poll();
                t.left = new TreeNode(val);
                t.right = new TreeNode(val);
                k -= 2;
                q.offer(t.left);
                q.offer(t.right);
            } else {
                TreeNode t = q.poll();
                t.left = new TreeNode(val);
                k--;
                q.offer(t.left);
            }
        }
        return res;
    }
}