二叉搜索树的第k大节点

Leetcode Link: 剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）

题目

解法一：纯暴力+暴力改

思路：

1. 纯暴力：暴力一点，直接使用 bfs 或者 dfs 遍历所有的节点，把所有的值保存到一起，最后排序后输出第 k 大的。

2. 暴力改：利用好二叉搜索树的性质，遍历时采用右→中→左的顺序，得到的值列表就不用排序了，自然就是从大到小，此时直接输出 lst[k] 即可

这两种方法都没啥意义。

解法二：利用二叉搜索树的性质提前退出

思路： 我们在暴力改的基础上可以提前退出。

一旦当前的lst长度==k，就说明我们找到了第k大的数字，后面的不用再看，直接退出bfs，返回结果即可。

题解：

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        val_lst = [] # 存储节点值
        def bfs(node):
            nonlocal k
            # base case
            if not node: return False
            
            if bfs(node.right): return True
            val_lst.append(node.val)
            if len(val_lst) == k: return True #找打了第k大的数字，可停止递归
            if bfs(node.left): return True
 
            return False
        
        bfs(root)
        return val_lst[-1]

这里，我们利用返回 True 和 False 提前退出递归。

总感觉这个解法的代码不是很优雅。

解法三

思路： 可以直接计数就行，而且提前返回可以以case的方式返回，而不是以True和False的方式返回。

题解：

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        res = None
        def dfs(node):
            nonlocal k, res
            # base case
            if not node: return
 
            dfs(node.right)
            # 提前返回的case
            if k == 0: return
			# 在逆中序位置操作
            k -= 1 
            if k == 0: res = node.val
 
            dfs(node.left)
 
        dfs(root)
        return res

启发和联系