โปรแกรมตรวจสอบลำดับ inorder ของ tree เป็น palindrome หรือไม่ ใน Python

สมมติว่าเรามีไบนารีทรีที่แต่ละโหนดมีตัวเลขตั้งแต่ 0-9 เราต้องตรวจสอบว่าการข้ามผ่านในลำดับนั้นเป็นพาลินโดรมหรือไม่

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นเอาต์พุตจะเป็น True เนื่องจากการส่งผ่านแบบไม่เรียงลำดับคือ [2,6,10,6,2]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้ารูทเป็นโมฆะ
  • คืนค่า True
• stack :=สแต็คใหม่
• curr :=root
• ไม่เป็นระเบียบ :=รายการใหม่
• ในขณะที่สแต็กไม่ว่างหรือเคอร์เซอร์ไม่เป็นโมฆะ ให้ทำ
  • ในขณะที่ curr ไม่เป็นค่าว่าง ให้ทำ
    • ดันเคอร์รี่เข้ากอง
    • curr :=ด้านซ้ายของสกุลเงิน
  • โหนด :=องค์ประกอบที่ปรากฏขึ้นจากสแต็ก
  • ใส่ค่าของโหนดที่ส่วนท้ายของ inorder
  • curr :=ด้านขวาของโหนด
• คืนค่า จริง เมื่อ inorder เหมือนกับ inorder ในลำดับที่กลับกัน มิฉะนั้น จะเป็นเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

True