สมมติว่าเรามีแผนผังการค้นหาแบบไบนารี และจำนวนเต็ม k อีกอัน เราต้องหาค่าที่น้อยที่สุดที่ k ในแผนผัง
ดังนั้นหากอินพุตเป็นแบบ
k =3 แล้วผลลัพธ์จะเป็น 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
stack :=stack เปล่า
-
ผม :=0
-
ตอบ :=-1
-
ในขณะที่สแต็กไม่ว่างหรือรูทไม่ว่างให้ทำ
-
ในขณะที่รูทไม่เป็นโมฆะให้ทำ
-
ดันรูทลงในสแต็ก
-
root :=เหลือรูท
-
-
v :=องค์ประกอบป๊อปจากสแต็ก
-
ถ้าฉันเหมือนกับ k แล้ว
-
ans :=ค่าของ v
-
ออกจากวง
-
-
root :=ด้านขวาของ v
-
ผม :=ผม + 1
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
ผลลัพธ์
7
