题解 | #牛群的二叉树排序# 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;
    }
}

代码使用的编程语言是Java。

该题考察的知识点是二叉树和深度优先搜索（DFS）。

代码的文字解释如下：

首先定义了一个公共类Solution，其中包含一个公共方法maxDepth。

maxDepth方法接收一个树的根节点root作为参数，并返回二叉树的最大深度。

在方法中，定义了一个私有变量ans，用于保存最大深度的结果。

使用深度优先搜索（DFS）来计算二叉树的最大深度。

定义了一个私有方法dfs，用于进行深度优先搜索。

在dfs方法中，首先判断当前节点是否为空，如果为空则直接返回。

如果当前节点是叶子节点（即没有左子节点和右子节点），比较当前深度cnt和ans的值，将较大的值更新给ans。

然后，递归调用dfs方法处理左子树和右子树。

在递归调用前，将深度cnt加1传递给下一层递归。

最后，将最终的ans作为结果返回。