Chương trình kiểm tra xem chuỗi inorder của cây có phải là palindrome hay không bằng Python

Giả sử chúng ta có một cây nhị phân trong đó mỗi nút chứa một chữ số từ 0-9, chúng ta phải kiểm tra xem liệu trình duyệt theo thứ tự của nó có phải là palindrome hay không.

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

thì kết quả đầu ra sẽ là True, vì đường đi ngang của nó là [2,6,10,6,2].

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

• nếu gốc là null, thì
  • trả về True
• ngăn xếp:=một ngăn xếp mới
• curr:=root
• inorder:=một danh sách mới
• while stack không trống hoặc curr không rỗng, hãy thực hiện
  • trong khi curr không phải là null, hãy thực hiện
    • đẩy cuộn dây vào ngăn xếp
    • curr:=left of curr
  • node:=phần tử được bật ra từ ngăn xếp
  • chèn giá trị của nút vào cuối inorder
  • curr:=right of node
• trả về true khi inorder giống với inorder theo thứ tự ngược lại, nếu không thì false.

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, root):
      if not root:
         return True
      stack = []
      curr = root
      inorder = []
      while stack or curr:
         while curr:
            stack.append(curr)
            curr = curr.left
         node = stack.pop() inorder.append(node.val)
         curr = node.right
      return inorder == inorder[::-1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

Đầu vào

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

Đầu ra

True