यह जाँचने के लिए प्रोग्राम कि क्या किसी पेड़ का क्रमागत क्रम पाइथॉन में पैलिंड्रोम है या नहीं

मान लीजिए कि हमारे पास एक बाइनरी ट्री है जहां प्रत्येक नोड में 0-9 से एक अंक होता है, हमें यह जांचना होगा कि इसका इन-ऑर्डर ट्रैवर्सल पैलिंड्रोम है या नहीं।

तो, अगर इनपुट पसंद है

तब आउटपुट ट्रू होगा, क्योंकि इसका इनऑर्डर ट्रैवर्सल [2,6,10,6,2] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यदि रूट रिक्त है, तो
  • सही लौटें
• स्टैक:=एक नया स्टैक
• करी :=जड़
• इनऑर्डर :=एक नई सूची
• जबकि स्टैक खाली नहीं है या curr null नहीं है, करें
  • जबकि curr शून्य नहीं है, करें
    • करी को ढेर में धकेलें
    • curr :=curr के बाएँ
  • नोड:=स्टैक से पॉप किया गया तत्व
  • इनऑर्डर के अंत में नोड का मान डालें
  • curr :=नोड के दाईं ओर
• सही लौटें जब इनऑर्डर विपरीत क्रम में इनऑर्डर के समान हो, अन्यथा गलत हो।

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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