文章目录
- 题目要求
- 解题思路
- 利用性质迭代
- 知识点
题目要求
给定一棵二叉搜索树,请找出其中第k大的节点。
解题思路
利用性质迭代
利用性质:二叉搜索树的中序遍历是递减的,因此二叉搜索树中序遍历的倒序是递增的。
二叉树的中序遍历:
recursive(root.left)
print(root.val)
recursive(root.right)
此外:
- 每当遍历到root的时候,k要减1。
- k == 0时,将root.val作为结果存储。
- 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
知识点
- python类中的__init__,是每次Class被实例化就会自动执行一次。
- self.name可以在类内被任意调用。本题中的,self.k和self.res也是如此。










