用 Python 编写程序，查找二叉搜索树中第 k 个最小元素

pythonserver side programmingprogramming更新于 2026/1/17 21:32:17

假设我们有一个二叉搜索树，还有另一个整数 k，我们需要找到树中第 k 个最小值。

因此，如果输入如下

k = 3，则输出为 7

要解决这个问题，我们将遵循以下步骤 −

stack := 一个空栈
i := 0
ans := -1
当堆栈不为空或根不为空时，执行
- 当根不为空时，执行
  - 将根推入堆栈
  - root := 根的左侧
- v := 从堆栈弹出元素
- 如果 i 与 k 相同，则
  - ans := v 的值
  - 退出循环
- root := v 的右侧
- i := i + 1
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None

class Solution:
   def solve(self, root, k):
      stack = []
      i = 0
      ans = -1
      while stack or root:
         while root:
            stack.append(root)
               root = root.left
         v = stack.pop()
         if i == k:
            ans = v.val
            break
         root = v.right
         i += 1
      return ans
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root, 3))

输入

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
3