หา Complete Subtree ใหญ่ที่สุดใน Binary Tree ด้วย Python

ค้นหา Complete Subtree ที่มีขนาดใหญ่ที่สุด

Complete Binary Tree คือต้นไม้ไบนารีที่ทุกระดับเต็มไปด้วยโหนด ยกเว้นระดับสุดท้ายที่อาจไม่เต็ม และโหนดในระดับสุดท้ายต้องชิดซ้ายมากที่สุด

โจทย์: หาขนาด (จำนวนโหนด) ของ Complete Subtree ที่ใหญ่ที่สุดใน Binary Tree ที่กำหนด

แนวคิดการแก้ปัญหา

ใช้การท่องต้นไม้แบบ Post-order พร้อมเก็บข้อมูลของแต่ละโหนด:

• isPerfect: เป็น Perfect Binary Tree หรือไม่ (ทุกระดับเต็ม)
• isComplete: เป็น Complete Binary Tree หรือไม่
• size: จำนวนโหนดใน Subtree ที่รากที่โหนดนี้
• rootTree: รากของ Complete Subtree ใหญ่ที่สุดใน Subtree นี้

เงื่อนไขสำคัญ:

1. ถ้าต้นซ้ายเป็น Perfect และต้นขวาเป็น Complete และความสูงเท่ากัน → โหนดปัจจุบันเป็น Complete (และ Perfect ถ้าต้นขวา Perfect)
2. ถ้าต้นซ้ายเป็น Complete และต้นขวาเป็น Perfect และความสูงซ้าย = ความสูงขวา + 1 → โหนดปัจจุบันเป็น Complete (แต่ไม่ Perfect)
3. มิฉะนั้น โหนดปัจจุบันไม่ใช่ Complete → เลือก Complete Subtree ใหญ่สุดจากลูกซ้ายหรือขวา

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

import math

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

class ReturnType:
    def __init__(self):
        self.isPerfect = False
        self.isComplete = False
        self.size = 0
        self.rootTree = None

def getHeight(size):
    return int(math.ceil(math.log(size + 1, 2)))

def checkCompleteness(root):
    ret = ReturnType()
    if root is None:
        ret.isPerfect = True
        ret.isComplete = True
        ret.size = 0
        ret.rootTree = None
        return ret

    left = checkCompleteness(root.left)
    right = checkCompleteness(root.right)

    # Case 1: Left Perfect, Right Complete, same height
    if left.isPerfect and right.isComplete and getHeight(left.size) == getHeight(right.size):
        ret.isComplete = True
        ret.isPerfect = right.isPerfect
        ret.size = left.size + right.size + 1
        ret.rootTree = root
        return ret

    # Case 2: Left Complete, Right Perfect, left height = right height + 1
    if left.isComplete and right.isPerfect and getHeight(left.size) == getHeight(right.size) + 1:
        ret.isComplete = True
        ret.isPerfect = False
        ret.size = left.size + right.size + 1
        ret.rootTree = root
        return ret

    # Not complete at this node
    ret.isPerfect = False
    ret.isComplete = False
    ret.size = max(left.size, right.size)
    ret.rootTree = left.rootTree if left.size > right.size else right.rootTree
    return ret

def print_inorder(root):
    if root:
        print_inorder(root.left)
        print(root.data, end=', ')
        print_inorder(root.right)

# ตัวอย่าง
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)

ans = checkCompleteness(root)
print("Size:", ans.size)
print("Inorder Traversal:", end=' ')
print_inorder(ans.rootTree)
# Output: Size: 4, Inorder: 10, 45, 60, 70,