หาย่อยต้นไม้บाइनนารีแบบสมบูรณ์ที่ใหญ่ที่สุดใน Python

สมมติว่าเรามีต้นไม้บाइनนารี ต้องการหาขนาดของย่อยต้นไม้แบบสมบูรณ์ (Perfect Binary Tree) ที่ใหญ่ที่สุด ย่อยต้นไม้แบบสมบูรณ์คือต้นไม้ที่ทุกโหนดภายในมีลูก 2 ด้าน และใบไม้ทุกใบอยู่ระดับเดียวกัน

เช่น ต้นไม้ตัวอย่าง ผลลัพธ์คือ 3 (ย่อยต้นไม้ที่มีราก 3 และใบ 5, 6)

ขั้นตอนการแก้ปัญหา (Post-order Traversal)

1. สร้างคลาส RetType เก็บ: isPerfect, height, rootTree
2. ฟังก์ชัน get_perfect_subtree(root):
   • ถ้า root เป็น None: คืนค่า isPerfect=True, height=0
   • เรียกซ้ำซ้ายและขวา
   • ถ้าทั้งสองสมบูรณ์และสูงเท่ากัน: รวมเป็นสมบูรณ์ height+1
   • มิฉะนั้น: ไม่สมบูรณ์ เลือกย่อยต้นไม้ที่สูงกว่า
3. ขนาด = 2^height - 1

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

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

class RetType:
    def __init__(self):
        self.isPerfect = False
        self.height = 0
        self.rootTree = None

def get_perfect_subtree(root):
    r_type = RetType()
    if root is None:
        r_type.isPerfect = True
        r_type.height = 0
        r_type.rootTree = None
        return r_type
    left_subtree = get_perfect_subtree(root.left)
    right_subtree = get_perfect_subtree(root.right)
    if left_subtree.isPerfect and right_subtree.isPerfect and left_subtree.height == right_subtree.height:
        r_type.height = left_subtree.height + 1
        r_type.isPerfect = True
        r_type.rootTree = root
        return r_type
    r_type.isPerfect = False
    r_type.height = max(left_subtree.height, right_subtree.height)
    if left_subtree.height > right_subtree.height:
        r_type.rootTree = left_subtree.rootTree
    else:
        r_type.rootTree = right_subtree.rootTree
    return r_type

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)
res = get_perfect_subtree(root)
h = res.height
print("Size:", 2**h - 1)
print("Tree:", end=" ")
# inorder print of res.rootTree

อินพุต

root = TreeNode(2) ... (ต้นไม้ตัวอย่าง)

เอาต์พุต

Size: 3 Tree: 5, 3, 6,