Giả sử chúng ta có một cây nhị phân. Chúng ta phải kiểm tra xem cây có phải là cây đối xứng hay không. Một cái cây sẽ được cho là đối xứng nếu nó giống nhau khi chúng ta chụp ảnh phản chiếu của nó. Từ hai cây này, cây đầu tiên là đối xứng, nhưng cây thứ hai thì không.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau.
- Chúng tôi sẽ gọi các bước sau một cách đệ quy. Hàm sẽ được giải quyết (root, root)
- nếu node1 và node2 trống, thì trả về true
- nếu node1 hoặc node2 trống, thì trả về false
- trả về true khi node1.val =node2.val và giải quyết (node1.left, node2.right) và giải quyết (node1.right, node2.left)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ return self.solve(root,root) def solve(self,node1,node2): if not node1 and not node2: return True if not node1 or not node2: return False # print(node1.val, node2.val) return node1.data == node2.data and self.solve(node1.left,node2.right) and self.solve(node1.right,node2.left) tree1 = make_tree([1,2,2,3,4,4,3]) tree2 = make_tree([1,2,2,3,4,None,3]) ob1 = Solution() print(ob1.isSymmetric(tree1)) print(ob1.isSymmetric(tree2))
Đầu vào
tree1 = make_tree([1,2,2,3,4,4,3]) tree2 = make_tree([1,2,2,3,4,None,3])
Đầu ra
True False