剑指 Offer 54. 二叉搜索树的第k大节点

剑指 Offer 54. 二叉搜索树的第k大节点https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

中序遍历 为 “左、根、右” 顺序，递归法代码如下： 

# 打印中序遍历
def dfs(root):
    if not root: return
    dfs(root.left)  # 左
    print(root.val) # 根
    dfs(root.right) # 右

 

第一种方法，中序遍历二叉树，输出倒数第k个

class Solution:
    def kthLargest(self, root, k):
        lst=[]
        def dfs(cur):
            if not cur: return
            dfs(cur.left)
            lst.append(cur.val)
            dfs(cur.right)
        dfs(root)
        return lst[len(lst)-k]

本文解法基于此性质：二叉搜索树的中序遍历为 递增序列 。

根据以上性质，易得二叉搜索树的 中序遍历倒序 为 递减序列 。
因此，求 “二叉搜索树第 k大的节点” 可转化为求 “此树的中序遍历倒序的第 k个节点”

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

如果，不想加nonlocal，则就把变量设置成self.xxx的形式，此时相当于全局变量，哪里都可以使用 

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