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. Chúng ta có thể gọi chúng là cây song sinh (twin trees).
Ví dụ, nếu đầu vào như hình:
thì đầu ra sẽ là True cho cặp đầu tiên, False cho cặp thứ hai và ba vì giá trị và cấu trúc khác nhau tương ứng.
Để giải quyết, chúng ta thực hiện các bước sau:
- Định nghĩa phương thức solve(), nhận hai root
- nếu root0 null và root1 null, trả về True
- nếu root0 null hoặc root1 null, trả về False
- nếu giá trị root0 khác giá trị root1, trả về False
- trả về True khi solve(left của root0, left của root1) VÀ solve(right của root0, right của root1) đều True, ngược lại False
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))
Input
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)
Output
True