โปรแกรมหาองค์ประกอบที่เล็กที่สุดลำดับที่ K ในต้นไม้ค้นหาไบนารีด้วย Python

สมมติว่าเรามีต้นไม้ค้นหาไบนารี (BST) และจำนวนเต็ม k เราต้องการหาค่าที่เล็กที่สุดลำดับที่ k ในต้นไม้ (1-indexed หรือ 0-indexed ตามการ implement)

ตัวอย่างเช่น หากอินพุตเป็นต้นไม้ BST ดังรูป และ k = 3 ผลลัพธ์จะเป็น 7

ขั้นตอนการแก้ปัญหา (Iterative Inorder Traversal with Stack)

1. stack = [], i = 0, ans = -1
2. วนลูป while stack หรือ root ไม่ใช่ null:
   • วนลูป while root ไม่ใช่ null:
     • push root เข้า stack
     • root = root.left
   • v = stack.pop()
   • หาก i == k ให้ ans = v.val และ break
   • root = v.right
   • i += 1
3. คืนค่า ans

ตัวอย่างโค้ด Python

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))  # Output: 7

อินพุต

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

เอาต์พุต

7