Python查找二叉搜索树第k大节点算法解析

山间有风

发布时间：2026-10-13| 5人浏览过

原创

本文介绍利用Python查找二叉搜索树（BST）中第k大节点的方法。核心思路基于中序遍历，通过递归方式在遍历过程中递减计数器k，当k减至1时即找到目标节点。文章提供了两种递归实现代码，无需额外数组空间，直接返回节点值，适合Python开发者参考学习。

本文通过具体实例展示如何使用Python代码查找二叉搜索树中第k大的节点，内容供读者参考学习。

题目描述

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

该问题的解决依赖于中序遍历过程。无需借助额外的数组存储节点，只需在遍历到节点时将计数器k减1，当k为1时即可确定目标节点。

代码1

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def __init__(self):
    self.k = 0
  def recursionKthNode(self, Root):
    result = None
    if result == None and Root.left:
      result = self.recursionKthNode(Root.left)
    if result == None:
      if self.k == 1:
        return Root
      self.k -= 1
    if result == None and Root.right:
      result = self.recursionKthNode(Root.right)
    return result
  def KthNode(self, Root, k):
    if Root == None:
      return None
    self.k = k
    return self.recursionKthNode(Root)
Root = TreeNode(5)
Root.left = TreeNode(3)
Root.left.left = TreeNode(2)
Root.left.right = TreeNode(4)
Root.right = TreeNode(7)
Root.right.left = TreeNode(6)
Root.right.right = TreeNode(8)
print(Solution().KthNode(Root,3).val)

输出结果为：4

代码2

class TreeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None
class Solution:
  def __init__(self):
    self.k = 0
  def InOrder(self, Root):
    ans = None
    if Root:
      if ans == None and Root.left:
        ans = self.InOrder(Root.left)  #往左遍历
      if ans == None and self.k == 1:
        ans = Root           #遍历到目标节点
      if ans == None and self.k != 1:   #没有遍历到目标节点，k--
        self.k -= 1
      if ans == None and Root.right:   #往右遍历
        ans = self.InOrder(Root.right)
    return ans
  def KthNode(self, Root, k):
    if Root == None or k <= 0:
      return None
    self.k = k
    return self.InOrder(Root)

如果您对Python技术感兴趣，可进一步查阅本站相关专题，包括《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》以及《Python入门与进阶经典教程》。

希望上述内容能对您的Python程序设计工作提供有益帮助。