Cho hai cây nhị phân. Kiểm tra tại mỗi level (độ sâu), tập giá trị nút của cây 1 có phải anagram (hoán vị) của cây 2 không.
Ví dụ: cây 1 level 1: [6,7], cây 2 level 1: [7,6] → anagram → True.
Thuật toán BFS
- Dùng 2 queue duyệt level-order đồng thời.
- Mỗi level: thu thập giá trị nút vào list, sort, so sánh.
- Nếu kích thước level khác nhau hoặc list sort khác →
False.
Triển khai
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def make_tree(elements):
root = TreeNode(elements[0])
for el in elements[1:]:
insert_value(root, el)
return root
def insert_value(root, value):
q = [root]
while q:
node = q.pop(0)
if not node.left:
node.left = TreeNode(value) if value is not None else TreeNode(0)
break
else:
q.append(node.left)
if not node.right:
node.right = TreeNode(value) if value is not None else TreeNode(0)
break
else:
q.append(node.right)
def solve(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
q1, q2 = [t1], [t2]
while q1:
if len(q1) != len(q2):
return False
if len(q1) == 0:
break
level1, level2 = [], []
for _ in range(len(q1)):
n1 = q1.pop(0)
if n1.left: q1.append(n1.left)
if n1.right: q1.append(n1.right)
level1.append(n1.value)
n2 = q2.pop(0)
if n2.left: q2.append(n2.left)
if n2.right: q2.append(n2.right)
level2.append(n2.value)
if sorted(level1) != sorted(level2):
return False
return True
t1 = make_tree([5, 6, 7, 9, 8])
t2 = make_tree([5, 7, 6, 8, 9])
print(solve(t1, t2)) # True
Đầu vào / Đầu ra
Input: [5,6,7,9,8], [5,7,6,8,9]
Output: True