Giả sử, chúng ta được cung cấp hai cây nhị phân. Chúng ta phải kiểm tra xem mỗi mức của một cây nhị phân có phải là một phép đảo ngữ của cùng một mức của cây nhị phân khác hay không. Chúng tôi trả về True nếu nó là một phép đảo chữ, nếu không, chúng tôi trả về False.
Vì vậy, nếu đầu vào giống như
, thì đầu ra sẽ là True.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- cây_1 là nút gốc của cây đầu tiên và cây_2 là nút gốc của cây thứ hai.
- nếu cây_1 giống null và cây_2 giống null, thì
- trả về True
- nếu cây_1 giống null hoặc cây_2 giống null, thì
- trả về Sai
- queue1:=một hàng đợi mới
- queue2:=một hàng đợi mới
- chèn cây_1 vào cuối hàng đợi1
- chèn cây_2 vào cuối hàng đợi2
- trong khi 1 khác 0, hãy thực hiện
- size1:=kích thước của hàng đợi1
- size2:=kích thước của hàng đợi2
- nếu size1 không giống với size2, thì
- trả về Sai
- nếu size1 giống 0, thì
- ra khỏi vòng lặp
- curr_level1:=một danh sách mới
- curr_level2:=một danh sách mới
- while size1> 0, do
- node1:=phần tử đầu tiên của queue1
- xóa phần tử đầu tiên khỏi queue1
- nếu bên trái của nút1 không giống với null, thì
- chèn bên trái của nút1 vào cuối hàng đợi1
- nếu bên phải của node1 không giống với null, thì
- chèn bên phải của nút1 vào cuối hàng đợi1
- size1:=size1 - 1
- node2:=phần tử đầu tiên của queue2
- xóa phần tử đầu tiên khỏi queue2
- nếu bên trái của node2 không giống với null, thì
- chèn bên trái của nút2 vào cuối hàng đợi2
- nếu bên phải của node2 không giống với null, thì
- chèn bên phải của nút2 vào cuối hàng đợi2
- chèn giá trị của node1 vào cuối curr_level1
- chèn giá trị của node2 vào cuối curr_level2
- sắp xếp danh sách curr_level1
- sắp xếp danh sách curr_level2
- nếu curr_level1 không giống với curr_level2, thì
- trả về Sai
- trả về True
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def make_tree(elements): tree = tree_node(elements[0]) for element in elements[1:]: insert_value(tree, element) return tree def insert_value(temp,value): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if value is not None: temp.left = tree_node(value) else: temp.left = tree_node(0) break else: que.append(temp.left) if (not temp.right): if value is not None: temp.right = tree_node(value) else: temp.right = tree_node(0) break else: que.append(temp.right) 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 == None and tree_2 == None) : return True if (tree_1 == None or tree_2 == None) : return False queue1 = [] queue2 = [] queue1.append(tree_1) queue2.append(tree_2) while (1) : size1 = len(queue1) size2 = len(queue2) if (size1 != size2): return False if (size1 == 0): break curr_level1 = [] curr_level2 = [] while (size1 > 0): node1 = queue1[0] queue1.pop(0) if (node1.left != None) : queue1.append(node1.left) if (node1.right != None) : queue1.append(node1.right) size1 -= 1 node2 = queue2[0] queue2.pop(0) if (node2.left != None) : queue2.append(node2.left) if (node2.right != None) : queue2.append(node2.right) curr_level1.append(node1.value) curr_level2.append(node2.value) curr_level1.sort() curr_level2.sort() if (curr_level1 != curr_level2) : return False return True tree_1 = make_tree([5, 6, 7, 9, 8]) tree_2 = make_tree([5, 7, 6, 8, 9]) print(solve(tree_1, tree_2))
Đầu vào
[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]
Đầu ra
True