สมมติว่าเรามีต้นไม้ไบนารี เราต้องหารายการที่มีการข้ามผ่านของรูทเป็นรายการ อย่างที่เราทราบกันดีว่าการข้ามผ่านแบบ inorder เป็นวิธีการข้ามโหนดทั้งหมดในต้นไม้ที่เรา -
-
ข้ามทรีย่อยด้านซ้ายซ้ำๆ
-
ข้ามโหนดปัจจุบัน
-
วนซ้ำในทรีย่อยด้านขวา
เราต้องพยายามแก้ปัญหานี้ซ้ำๆ
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น [12,13,4,16,7,14,22]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
inorder :=รายการใหม่
-
stack :=stack เปล่า
-
ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด ทำ
-
ถ้ารูทไม่เป็นโมฆะ
-
ดันรูทเข้าไปในสแต็ก
-
root :=เหลือรูท
-
-
มิฉะนั้นเมื่อสแต็กไม่ว่างเปล่า
-
root :=องค์ประกอบด้านบนของ stack และ pop จาก stack
-
แทรกค่าของรูทที่ส่วนท้ายของ inorder
-
root :=ด้านขวาของรูท
-
-
มิฉะนั้น
-
ออกจากวง
-
-
-
ส่งคืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None class Solution: def solve(self, root): inorder = [] stack = [] while True: if root: stack.append(root) root = root.left elif stack: root = stack.pop() inorder.append(root.val) root = root.right else: break return inorder ob = Solution() root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7) print(ob.solve(root))
อินพุต
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
ผลลัพธ์
[12, 13, 4, 16, 7, 14, 22]
