前往此题

中序遍历，递归解法

题目一开始已经明确了是一个二叉搜索树，它的特点就是右子树 > 根节点 > 左子树，我们可以按照这个特性进行从大到小遍历。

中序遍历一般是按照左子树->根节点->右子树的顺序是遍历的，这次我们反过来遍历

def dfs(root):
    if not root: return
    dfs(root.right) # 右
    print(root.val) # 根
    dfs(root.left)  # 左

算法过程

• 变量k作为计数，统计大小序号
• 变量res作为记录结果

1. 递归终止条件：当root为None,本次递归结束，返回上一层

2. 递归算法逻辑：

   • 当k == 0，直接返回当前节点
   • k = k -1逐层递减
   • 若k递减到0了，说明以及找到了第k大节点，将root.val保存到res中

3. 最后再递归左子树

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        def dfs(root):
            if not root: return
            dfs(root.right)
            if self.k == 0: return
            self.k -= 1
            if self.k == 0: self.res = root.val
            dfs(root.left)

        self.k = k
        dfs(root)
        return self.res

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度 : O(N)