โปรแกรมทำ Inorder Traversal แบบ Iterative บนต้นไม้ไบนารีใน Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหารายการที่มี inorder traversal (ซ้าย -> รูท -> ขวา) แบบ iterative (ไม่ใช้ recursion)

ตัวอย่าง: ต้นไม้ดังรูป ผลลัพธ์ [12, 13, 4, 16, 7, 14, 22]

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

1. inorder = [], stack = []
2. วนลูป while True:
   • หาก root ไม่ใช่ null: push root เข้า stack, root = root.left
   • มิฉะนั้น หาก stack ไม่ว่าง: pop จาก stack, เพิ่มค่าเข้า inorder, root = root.right
   • มิฉะนั้น: break
3. คืนค่า inorder

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

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))  # Output: [12, 13, 4, 16, 7, 14, 22]

อินพุต

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]