ধরুন আমাদের একটি বাইনারি ট্রি আছে যেখানে প্রতিটি নোডে 0-9 পর্যন্ত একটি ডিজিট রয়েছে, আমাদের চেক করতে হবে এর ইন-অর্ডার ট্রাভার্সাল প্যালিনড্রোম কিনা।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে True, কারণ এর ইনঅর্ডার ট্রাভার্সাল হল [2,6,10,6,2]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- যদি রুট নাল হয়, তাহলে
- সত্য ফেরান
- স্ট্যাক :=একটি নতুন স্ট্যাক
- curr :=root
- অনুক্রম :=একটি নতুন তালিকা
- স্ট্যাক খালি না থাকা অবস্থায় বা curr শূন্য না হলে
- করুন
- যদিও curr নাল না হয়, do
- স্ট্যাকের মধ্যে curr পুশ করুন
- curr :=curr এর বাম
- নোড :=স্ট্যাক থেকে পপ করা উপাদান
- ইনঅর্ডারের শেষে নোডের মান সন্নিবেশ করান
- curr :=নোডের ডানদিকে
- যদিও curr নাল না হয়, do
- সত্য প্রত্যাবর্তন করুন যখন ইনঅর্ডার বিপরীত ক্রমে ইনঅর্ডারের মতো হয়, অন্যথায় মিথ্যা৷
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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
