Chương trình kiểm tra trình tự các lá có giống nhau của hai lá hay không trong python

Giả sử chúng ta có hai cây nhị phân; chúng ta phải kiểm tra xem trình tự của các lá từ trái sang phải ở cả hai cây có giống nhau hay không.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True vì trình tự là [2, 6] cho cả hai cây.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• c:=một danh sách mới
• Xác định một hàm inorder (). Điều này sẽ bén rễ và c
• nếu c là null, thì
  • c:=một danh sách mới
• nếu root không null, thì
  • inorder (bên trái của thư mục gốc, c)
  • nếu bên trái của thư mục gốc là null và bên phải của thư mục gốc là null, thì
    • chèn giá trị gốc vào cuối c
  • inorder (bên phải của thư mục gốc, c)
• trả về c
• Từ phương pháp chính, hãy thực hiện như sau:
• nếu inorder (root0) giống với inorder (root1), thì
  • trả về True
• nếu không,
  • trả về 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, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right

class Solution:
   c = []

   def inorder(self, root, c=None):
      if c is None:
         c = []
      if root:
         self.inorder(root.left, c)
         if not root.left and not root.right:
            c.append(root.val)
            self.inorder(root.right, c)
      return c

   def solve(self, root0, root1):
      if self.inorder(root0) == self.inorder(root1):
         return True
      else:
         return False

ob = Solution()
root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6)

root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)
print(ob.solve(root1, root2))

Đầu vào

root1 = TreeNode(1)
root1.right = TreeNode(3)
root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6) 

root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)
root2.left.left = TreeNode(2)

Đầu ra

True