โปรแกรมกลับด้านต้นไม้ไบนารี (Invert Binary Tree) ใน Python

สมมติว่าเรามีต้นไม้ไบนารี root เราต้องกลับด้าน (invert) มัน โดยสลับ subtree ซ้ายและขวา และลูกของพวกเขาแบบ recursive

ตัวอย่าง: ก่อน invert และหลัง invert (ดูรูป)

ขั้นตอนการแก้ปัญหา (Recursive Swap)

1. หาก root เป็น null ให้คืนค่า
2. root.left, root.right = solve(root.right), solve(root.left)
3. คืนค่า root

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

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=', ')
        inorder(root.right)

class Solution:
    def solve(self, root):
        if not root:
            return
        root.left, root.right = self.solve(root.right), self.solve(root.left)
        return root

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
inv = ob.solve(root)
inorder(inv)  # Output: 15, 10, 7, 5, 4,

อินพุต

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

เอาต์พุต

15, 10, 7, 5, 4,