Chương trình tìm phần tử nhỏ nhất thứ k trong Cây tìm kiếm nhị phân bằng Python

Giả sử chúng ta có một cây tìm kiếm nhị phân và một số nguyên k khác, chúng ta phải tìm giá trị nhỏ nhất thứ k trong cây.

Vì vậy, nếu đầu vào giống như

k =3, thì đầu ra sẽ là 7

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• stack:=một ngăn xếp trống

• i:=0

• ans:=-1

• trong khi ngăn xếp không trống hoặc gốc không rỗng, hãy thực hiện

  • trong khi root không null, thực hiện

    • đẩy root vào ngăn xếp

    • root:=left of root

  • v:=phần tử pop từ ngăn xếp

  • nếu tôi giống với k, thì

    • ans:=giá trị của v

    • đi ra từ vòng lặp

  • root:=right of v

  • i:=i + 1

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

7