Kiểm tra xem đường đi ngang qua lá của hai Cây nhị phân có giống nhau trong Python hay không

Giả sử chúng ta có hai cây nhị phân. Chúng ta phải kiểm tra xem chiều chuyển lá của hai cây này có giống nhau hay không. Như chúng ta đã biết hành trình ngang lá là một chuỗi các lá đi ngang từ trái sang phải.

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

thì đầu ra sẽ là True vì trình tự duyệt bên trái của cả hai cây đều giống nhau, nghĩa là [5, 7, 8].

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

s1:=một danh sách mới, s2:=một danh sách mới khác
chèn r1 vào s1 và r2 vào s2
trong khi s1 và s2 không trống, hãy thực hiện
- nếu s1 trống hoặc s2 trống, thì
  - trả về Sai
- r1_node:=nút cuối cùng của s1 và xóa nó khỏi s1
- trong khi r1_node không giống với null và r1_node không phải là lá, hãy thực hiện
  - nếu bên phải của r1_node không giống với null, thì
    - chèn bên phải r1_node vào cuối s1
  - nếu bên trái của r1_node không giống với null, thì
    - chèn bên trái của r1_node vào cuối s1
    - r1_node:=nút cuối cùng của s1 và xóa nó khỏi s1
- r2_node:=nút cuối cùng của s2 và xóa nó khỏi s2
- trong khi r2_node không phải là null và r2_node không phải là lá, hãy thực hiện
  - nếu bên phải của r2_node không rỗng, thì
    - chèn bên phải r2_node vào cuối s2
  - nếu bên trái của r2_node không phải là null, thì
    - chèn bên trái của r2_node vào cuối s2
  - r2_node:=nút cuối cùng của s2 và xóa nó khỏi s2
- nếu r1_node là null và r2_node không phải là null, thì
  - trả về Sai
- nếu r1_node không phải là null và r2_node là null, thì
  - trả về Sai
- nếu cả r1_node và r2_node đều không rỗng thì
  - nếu giá trị của r1_node không giống với giá trị của r2_node, thì
    - trả về Sai
trả về True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class TreeNode:
   def __init__(self, x):
      self.val = x
      self.left = self.right = None
   def is_leaf(self):
      return self.left == None and self.right == None
def solve(r1, r2):
   s1 = []
   s2 = []
   s1.append(r1)
   s2.append(r2)
   while len(s1) != 0 or len(s2) != 0:
      if len(s1) == 0 or len(s2) == 0:
         return False
      r1_node = s1.pop(-1)
      while r1_node != None and not r1_node.is_leaf():
         if r1_node.right != None:
            s1.append(r1_node.right)
         if r1_node.left != None:
            s1.append(r1_node.left)
            r1_node = s1.pop(-1)
      r2_node = s2.pop(-1)
      while r2_node != None and not r2_node.is_leaf():
         if r2_node.right != None:
            s2.append(r2_node.right)
         if r2_node.left != None:
            s2.append(r2_node.left)
         r2_node = s2.pop(-1)
      if r1_node == None and r2_node != None:
         return False
      if r1_node != None and r2_node == None:
   return False
if r1_node != None and r2_node != None:
if r1_node.val != r2_node.val:
return False
return True
root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)
print(solve(root1, root2))

Đầu vào

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

Đầu ra

True