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

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

25

文章目录

    • 题目要求
    • 解题思路
      • 利用性质迭代
    • 知识点

题目要求

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

解题思路

利用性质迭代

利用性质:二叉搜索树的中序遍历是递减的,因此二叉搜索树中序遍历的倒序是递增的。

二叉树的中序遍历:

recursive(root.left)
print(root.val)
recursive(root.right)

此外:

  1. 每当遍历到root的时候,k要减1。
  2. k == 0时,将root.val作为结果存储。
  3. k == 0时,停止迭代。
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def kthLargest(self, root, k):""":type root: TreeNode:type k: int:rtype: int"""def recursive(root):# 若根节点为空,则停止本次迭代。if not root:return# 先右节点。recursive(root.right)# 若self.k等于0,则提前终止迭代。if self.k <= 0:return# 到root节点时,执行k减1的操作,且当self.k为0时,证明找到第k大的数了,记录之。self.k -= 1if self.k == 0:self.res =  root.val# 再左节点。recursive(root.left)self.k = krecursive(root)return self.res

知识点

  1. python类中的__init__,是每次Class被实例化就会自动执行一次。
  2. self.name可以在类内被任意调用。本题中的,self.k和self.res也是如此。