Sword finger offer 54. the k-th node of the binary search tree

The finger of the sword Offer 54. The second of binary search tree k Big node https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

In the sequence traversal   by “ Left 、 root 、 Right ” The order , The recursive method code is as follows ： 

#  Print sequence traversal 
def dfs(root):
    if not root: return
    dfs(root.left)  #  Left 
    print(root.val) #  root 
    dfs(root.right) #  Right 

 

The first method , Middle order ergodic binary tree , Output the last of k individual

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]

The solution in this paper is based on this property ： The middle order traversal of binary search tree is Increasing sequence .

According to the above properties , Easy to get binary search tree The middle order traverses the reverse order by Decreasing sequence .
therefore , seek “ Binary search tree No k Big nodes ” It can be transformed into seeking “ The middle order of this tree traverses the reverse order k Nodes ”

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

If , I don't want to add nonlocal, Then set the variable to self.xxx In the form of , This is equivalent to a global variable , Can be used anywhere  

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