สมมติว่าเรามีแผนผังการค้นหาแบบไบนารี เราต้องหาองค์ประกอบที่เล็กที่สุดของ Kth ใน BST นั้น ดังนั้นถ้าต้นไม้เป็นเหมือน −
ดังนั้นหากเราต้องการหาองค์ประกอบที่เล็กที่สุดอันดับ 3 แล้ว k =3 และผลลัพธ์จะเป็น 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างรายการว่างที่เรียกว่าโหนด
- เรียกแก้ปัญหา (รูท, โหนด)
- คืนค่า k – องค์ประกอบที่ 1 ของโหนด
- วิธีการแก้ปัญหาถูกสร้างขึ้น ซึ่งจะทำการรูทและโหนดอาร์เรย์ ซึ่งจะทำงานดังนี้ -
- ถ้ารูทเป็นโมฆะ ให้ส่งคืน
- แก้ (ด้านซ้ายของรูท, โหนด)
- เพิ่มค่าของรูทลงในอาร์เรย์โหนด
- แก้(ทางขวาของรูท, โหนด)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def kthSmallest(self, root, k): nodes = [] self.solve(root,nodes) return nodes[k-1] def solve(self, root,nodes): if root == None: return self.solve(root.left,nodes) nodes.append(root.data) self.solve(root.right,nodes) ob1 = Solution() tree = make_tree([10,5,15,2,7,13]) print(ob1.kthSmallest(tree, 3))
อินพุต
[10,5,15,2,7,13] 3
ผลลัพธ์
7
