本文共 949 字，大约阅读时间需要 3 分钟。

为了找到二叉搜索树中的第k大节点，我们可以采用中序遍历的方法。中序遍历将节点值按从小到大的顺序存储在一个列表中，然后取出倒数第k个元素即可得到第k大的节点。

步骤解析：

代码实现：

import java.util.ArrayList;import java.util.List;public class Solution {    public int kthLargest(TreeNode root, int k) {        List
   
     list = new ArrayList<>();        dfs(root, list);        return list.get(list.size() - k);    }    private void dfs(TreeNode root, List
    
      list) {        if (root == null) {            return;        }        dfs(root.left, list);        list.add(root.val);        dfs(root.right, list);    }}
    
   

代码解释：

• kthLargest方法：初始化一个空列表，调用递归函数dfs进行中序遍历，填充节点值到列表中。最后，返回列表中倒数第k个元素，即第k大的节点。

• dfs方法：递归遍历二叉树，首先处理左子树，然后将当前节点值添加到列表中，最后处理右子树。如果当前节点为null，递归终止。

这种方法通过中序遍历直接获取所需顺序，时间复杂度为O(n)，其中n为二叉树的节点数。空间复杂度为O(n)，用于存储中序遍历结果。该方法简洁高效，适用于给定的约束条件。

转载地址：http://bgwcz.baihongyu.com/