ปัญหา
กำหนด Binary Tree 2 ต้น ตรวจสอบว่าแต่ละ Level (ระดับ) ของ Tree 1 เป็น Anagram ของ Level เดียวกันใน Tree 2 หรือไม่
แนวทางแก้ปัญหา (BFS Level-order)
- ใช้ Queue 2 อัน สำหรับ Tree 1 และ 2
- ประมวลผลทีละ Level: ดึง Node ทั้ง Level, เก็บค่า, Push ลูกเข้า Queue
- Sort ค่าทั้งสอง Level แล้วเปรียบเทียบ
ตัวอย่างโค้ด
class tree_node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def solve(tree_1, tree_2):
if tree_1 is None and tree_2 is None: return True
if tree_1 is None or tree_2 is None: return False
queue1, queue2 = [tree_1], [tree_2]
while True:
size1, size2 = len(queue1), len(queue2)
if size1 != size2: return False
if size1 == 0: break
curr_level1, curr_level2 = [], []
for _ in range(size1):
node1 = queue1.pop(0)
if node1.left: queue1.append(node1.left)
if node1.right: queue1.append(node1.right)
curr_level1.append(node1.value)
node2 = queue2.pop(0)
if node2.left: queue2.append(node2.left)
if node2.right: queue2.append(node2.right)
curr_level2.append(node2.value)
if sorted(curr_level1) != sorted(curr_level2):
return False
return True
# ตัวอย่าง Tree
def make_tree(elements):
root = tree_node(elements[0])
for el in elements[1:]:
# insert level-order (simplified)
pass # implementation omitted for brevity
return root
tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2)) # Trueอินพุต / เอาต์พุต
Input: [5, 6, 7, 9, 8], [5, 7, 6, 8, 9] Output: True
