Chương trình kiểm tra xem hai cây có thể được hình thành bằng cách hoán đổi các nút hay không trong Python

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

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 -

• que1:=một hàng đợi với root0 ban đầu

• que2:=một hàng đợi với root1 ban đầu

• trong khi que1 và que2 không trống, thực hiện

  • temp1:=a new list, temp2:=a new list

  • giá trị1:=danh sách mới, giá trị2:=danh sách mới

  • nếu que1 và que2 chứa số phần tử khác nhau thì

    • trả về Sai

  • đối với tôi trong phạm vi từ 0 đến kích thước của que1 - 1, hãy thực hiện

    • chèn giá trị que1 [i] vào cuối giá trị1

    • chèn giá trị que2 [i] vào cuối giá trị2

    • nếu bên phải que1 [i] không rỗng thì

      • chèn bên phải que1 [i] vào cuối temp1

    • nếu bên trái của que1 [i] không rỗng, thì

      • chèn bên trái que1 [i] vào cuối temp1

    • nếu bên phải que2 [i] không rỗng thì

      • chèn bên phải que2 [i] vào cuối temp2

    • nếu bên trái của que2 [i] không phải là null, thì

      • chèn bên trái que2 [i] vào cuối temp2

  • nếu giá trị1 không giống như giá trị2, thì

    • nếu giá trị1 không giống với giá trị2 theo thứ tự ngược lại, thì

      • trả về Sai

  • que1:=temp1, que2:=temp2

• trả về True

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.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))

Đầu vào

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)

Đầu ra

True