মান ল করুন একটি বাইনারি ট্রি যেখানে প্রতিটি নোডে ০-৯ এর একটি ডিজিট থাকে, আমাদের যাচাই করতে হবে এর ইনঅর্ডার ট্রভারসাল প্যালিনড্রোম কিনা।
যদি ইনপুট হয়:
তবে আউটপুট হবে True, কারণ এর ইনঅর্ডার ট্রভারসাল [2,6,10,6,2]।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- যদি root null হয়, তবে True ফেরত দিন।
- stack := একটি নতুন স্ট্যাক, curr := root, inorder := একটি নতুন তালিকা
- যখন stack খালি না বা curr null না হয়:
- যখন curr null না হয়: curr কে stack-এ পুশ করুন, curr := curr.left
- node := stack থেকে পপ করুন, node.val কে inorder-এ যোগ করুন, curr := node.right
- inorder == inorder[::-1] হলে 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
