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

तो आउटपुट True होगा, क्योंकि इसका इनऑर्डर ट्रैवर्सल [2,6,10,6,2] है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- यदि root null है, तो
- True वापस करें
- stack := एक नया स्टैक
- curr := root
- inorder := एक नई सूची
- जब तक stack खाली नहीं है या curr null नहीं है, करें
- जब तक curr null नहीं है, करें
- curr को stack में पुश करें
- curr := curr का बायाँ
- node := stack से पॉप किया गया तत्व
- node के मान को inorder के अंत में जोड़ें
- curr := node का दायाँ
- जब तक curr null नहीं है, करें
- यदि inorder, उल्टे क्रम में inorder के समान है तो true वापस करें, अन्यथा false।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
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