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

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1

输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

输出: 4

限制：

• 1 ≤ k ≤ 二叉搜索树元素个数

Python 解答：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        target = None
        def traverse(root):
            if not root:
                return 
            else:
                traverse(root.right)
                nonlocal k, target
                k -= 1
                if k == 0:
                    target = root.val
                    return 
                traverse(root.left)
        traverse(root)
        return target