โจทย์: กำหนด Binary Tree หา subtree ใหญ่ที่สุดที่ left subtree และ right subtree เหมือนกัน (identical) O(n) time
อัลกอริทึม: Tree Encoding + Post-order
- Post-order traversal: เข้ารหัส (encode) โครงสร้าง subtree แต่ละโหนดเป็นสตริง
- encoding = "|" + left_encoding + "|" + node_value + "|" + right_encoding + "|"
- เปรียบเทียบ left_encoding และ right_encoding → ถ้าเหมือนกัน → subtree นี้ symmetric
- ติดตามขนาดใหญ่ที่สุด (maxSize) และโหนดราก (maxNode)
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def solve(root, encode, maxSize, maxNode):
if root is None:
return 0
left_list = [""]
right_list = [""]
ls = solve(root.left, left_list, maxSize, maxNode)
rs = solve(root.right, right_list, maxSize, maxNode)
size = ls + rs + 1
if left_list[0] == right_list[0]:
if size > maxSize[0]:
maxSize[0] = size
maxNode[0] = root
encode[0] = encode[0] + "|" + left_list[0] + "|"
encode[0] = encode[0] + "|" + str(root.data) + "|"
encode[0] = encode[0] + "|" + right_list[0] + "|"
return size
def largestSubtree(node, maxNode):
maximum = [0]
encode = [""]
solve(node, encode, maximum, maxNode)
return maximum
# ตัวอย่างต้นไม้
root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)
maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree:", maxNode[0].data)
print("and its size is:", maximum)
ผลลัพธ์
Root of largest sub-tree 70 and its size is [7]
สรุป: ใช้ encoding แทนการเปรียบเทียบต้นไม้โดยตรง O(n) time เพราะแต่ละโหนดประมวลผล 1 ครั้ง encoding ความยาวสัมพันธ์กับขนาด subtree
