Java题解 | #二叉树之寻找第k大#

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类
     * @param k int整型
     * @return int整型
     */
     private int result;
    private int count;
    public int kthLargest (TreeNode root, int k) {
        // write code here
        result = 0;
        count = 0;
        inorderTraversal(root, k);
        return result;
    }

    private void inorderTraversal(TreeNode node, int k) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.right, k);

        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        inorderTraversal(node.left, k);
    }
}

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

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 大的牛的编号。