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 root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
if (root == null) {
            return 0;
        }
        
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

该题考察的主要知识点有：

1. 二叉搜索树（Binary Search Tree，BST）：二叉搜索树是一种特殊类型的二叉树，其中每个节点的左子树中的所有节点都小于该节点，右子树中的所有节点都大于该节点。这种特性使得二叉搜索树可以方便地进行元素的查找和排序。
2. 中序遍历（Inorder Traversal）：中序遍历是二叉树遍历的一种方式，按照左子树、根节点、右子树的顺序访问节点。对于二叉搜索树来说，中序遍历会按照从小到大的顺序输出节点的值。
3. 递归（Recursion）：在解决二叉树相关问题时，常常会使用递归的方法。递归是一种自我调用的方法，在处理树结构时可以方便地处理子树问题。

代码的解释大纲如下：

1. 创建一个全局变量 result 用于记录第 k 大的节点值。
2. 创建一个全局计数器 count 并初始化为 0。
3. 定义一个递归函数 inorderTraversal，接收当前节点 node 和目标排名 k 作为参数。
4. 在 inorderTraversal 函数中，先递归遍历右子树，即 inorderTraversal(node.right, k)。
5. 在中序遍历的位置，进行如下操作：将计数器 count 自增 1。如果 count 等于目标排名 k，则将当前节点的值赋给 result 变量，并返回。否则，递归遍历左子树，即 inorderTraversal(node.left, k)。
6. 在主函数中，调用 inorderTraversal 函数，并传入根节点和目标排名 k，即 inorderTraversal(root, k)。
7. 返回 result 变量作为结果，即第 k 大的牛的编号。