Chương trình kiểm tra hai cây có thể biến đổi lẫn nhau bằng hoán vị nút con trong Python

Giả sử chúng ta có hai cây, chúng ta phải kiểm tra xem có thể biến đổi cây thứ nhất thành cây thứ hai bằng cách hoán vị (swap) cây con trái và phải của bất kỳ nút nào bất kỳ số lần nào hay không.

Ví dụ, nếu đầu vào như hình:

thì đầu ra sẽ là True

Để giải quyết, chúng ta thực hiện các bước sau:

• que1 := hàng đợi với root0 ban đầu
• que2 := hàng đợi với root1 ban đầu
• trong khi que1 và que2 không rỗng:
  • temp1 := danh sách mới, temp2 := danh sách mới
  • values1 := danh sách mới, values2 := danh sách mới
  • nếu que1 và que2 chứa số phần tử khác nhau, trả về False
  • với i từ 0 đến kích thước que1 - 1:
    • thêm giá trị que1[i] vào values1
    • thêm giá trị que2[i] vào values2
    • nếu right của que1[i] không null, thêm vào temp1
    • nếu left của que1[i] không null, thêm vào temp1
    • nếu right của que2[i] không null, thêm vào temp2
    • nếu left của que2[i] không null, thêm vào temp2
  • nếu values1 khác values2:
    • nếu values1 khác values2 đảo ngược, trả về False
  • que1 := temp1, que2 := temp2
• trả về True

Ví dụ

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root0, root1):
        que1 = [root0]
        que2 = [root1]
        while que1 and que2:
            temp1 = []
            temp2 = []
            values1 = []
            values2 = []
            if len(que1) != len(que2):
                return False
            for i in range(len(que1)):
                values1.append(que1[i].val)
                values2.append(que2[i].val)
                if que1[i].right:
                    temp1.append(que1[i].right)
                if que1[i].left:
                    temp1.append(que1[i].left)
                if que2[i].right:
                    temp2.append(que2[i].right)
                if que2[i].left:
                    temp2.append(que2[i].left)
            if values1 != values2:
                if values1 != values2[::-1]:
                    return False
            que1 = temp1
            que2 = temp2
        return True

ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
print(ob.solve(root, root1))

Input

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

Output

True