剑指 Offer54-二叉搜索树的第 k 大节点

兴趣爱好交流 每日一题
1

剑指 Offer54-二叉搜索树的第 k 大节点

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

示例 1:


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

   3

  / \

 1   4

  \

  2

输出: 4

示例 2:


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

       5

      / \

     3   6

    / \

   2   4

  /

 1

输出: 4

限制：

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

来源：力扣（LeetCode）

链接：力扣

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一解

使用“右中左”顺序遍历二叉树，利用 k 记录遍历次数（从最大到最小），若达到指定次数退出递归。


# 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:

        def rec(node):

            if not node: return

            rec(node.right)

            if self.k == 0: return

            self.k -= 1

            if self.k == 0: self.res = node.val

            rec(node.left)

        self.k = k

        rec(root)

        return self.res