Phần tử nhỏ thứ K trong cây tìm kiếm nhị phân (Kth Smallest Element in a BST) trong Python

Giả sử chúng ta có một cây tìm kiếm nhị phân (BST). Chúng ta phải tìm phần tử nhỏ thứ K trong BST đó. Ví dụ, nếu cây như sau:

Nếu ta muốn tìm phần tử nhỏ thứ 3, thì k = 3, kết quả sẽ là 7.

Để giải quyết, chúng ta làm theo các bước sau:

• Tạo danh sách rỗng tên cac_nut.

• Gọi giai_quyet(root, cac_nut).

• Trả về phần tử thứ k-1 của cac_nut.

• Phương thức giai_quyet nhận root và mảng cac_nut, hoạt động như sau:

  • Nếu root là null, trả về.
  • giai_quyet(left của root, cac_nut).
  • Thêm giá trị root vào mảng cac_nut.
  • giai_quyet(right của root, cac_nut).

Ví dụ

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

def chen(temp, data):
    hang_doi = []
    hang_doi.append(temp)
    while len(hang_doi):
        temp = hang_doi[0]
        hang_doi.pop(0)
        if not temp.left:
            temp.left = TreeNode(data)
            break
        else:
            hang_doi.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data)
            break
        else:
            hang_doi.append(temp.right)

def tao_cay(cac_phan_tu):
    Cay = TreeNode(cac_phan_tu[0])
    for phan_tu in cac_phan_tu[1:]:
        chen(Cay, phan_tu)
    return Cay

class Solution(object):
    def kthSmallest(self, root, k):
        cac_nut = []
        self.giai_quyet(root, cac_nut)
        return cac_nut[k-1]
    
    def giai_quyet(self, root, cac_nut):
        if root is None:
            return
        self.giai_quyet(root.left, cac_nut)
        cac_nut.append(root.data)
        self.giai_quyet(root.right, cac_nut)

ob1 = Solution()
cay = tao_cay([10,5,15,2,7,13])
print(ob1.kthSmallest(cay, 3))

Đầu vào

[10,5,15,2,7,13] 3

Đầu ra

7