Giả sử chúng ta có hai cây nhị phân, chúng ta phải kiểm tra xem chúng có hoàn toàn giống nhau về cấu trúc và giá trị hay không. Có thể nói chúng là cây sinh đôi.
Vì vậy, nếu đầu vào giống như
thì kết quả đầu ra sẽ là True cho cặp đầu tiên, false cho cặp thứ hai và cặp thứ ba vì đối với mục thứ hai và thứ ba là khác nhau và cấu trúc tương ứng cũng khác.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức giải quyết (), điều này sẽ có hai gốc
-
nếu root0 là null và root1 là null thì
-
trả về True
-
-
nếu root0 là null hoặc root1 là null thì
-
trả về Sai
-
-
nếu giá trị của root0 không giống với giá trị của root1, thì
-
trả về Sai
-
-
trả về true khi giải quyết (bên trái của root0, bên trái của root1) và giải quyết (bên phải của root0, bên phải của root1) là đúng, nếu không thì sai.
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, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def solve(self, root0, root1): if not root0 and not root1: return True if not root0 or not root1: return False if root0.val != root1.val: return False return self.solve(root0.left, root1.left) and self.solve(root0.right, root1.right) ob = Solution() root1 = TreeNode(10) root1.left = TreeNode(5) root1.right = TreeNode(15) root1.left.left = TreeNode(3) root1.left.right = TreeNode(8) root2 = TreeNode(10) root2.left = TreeNode(5) root2.right = TreeNode(15) root2.left.left = TreeNode(3) root2.left.right = TreeNode(8) print(ob.solve(root1, root2))
Đầu vào
root1 = TreeNode(10) root1.left = TreeNode(5) root1.right = TreeNode(15) root1.left.left = TreeNode(3) root1.left.right = TreeNode(8) root2 = TreeNode(10) root2.left = TreeNode(5) root2.right = TreeNode(15) root2.left.left = TreeNode(3) root2.left.right = TreeNode(8)
Đầu ra
True