题解 | #二叉树之寻找第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整型
     */
    public int kthLargest (TreeNode root, int k) {
        // write code here
        List<Integer> inorderValues = new ArrayList<>();
        inorderTraversal(root, inorderValues);

        return inorderValues.get(inorderValues.size() - k);
    }

    private void inorderTraversal(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.left, values);
        values.add(node.val);
        inorderTraversal(node.right, values);
    }
}

知识点：

1. 二叉搜索树（Binary Search Tree，BST）基本概念：了解二叉搜索树的定义和基本特点，包括左子树节点值小于根节点，右子树节点值大于根节点等。
2. 二叉搜索树的中序遍历：了解如何通过中序遍历二叉搜索树，得到有序的节点值序列。
3. 递归：理解递归在解决二叉树问题中的应用，特别是二叉搜索树的遍历和搜索。

题目解答方法：

要解决这个问题，可以通过中序遍历二叉搜索树，得到有序的节点值序列，然后根据索引找到编号第 k 大的牛的编号。

具体步骤如下：

1. 创建一个数组或链表，用于存储中序遍历得到的节点值序列。
2. 进行中序遍历二叉搜索树，将节点值按照从小到大的顺序加入数组或链表。
3. 根据给定的 k，找到数组或链表中对应索引位置的节点值，即编号第 k 大的牛的编号。