ধরুন আমাদের কাছে একটি বাইনারি গাছের ইনঅর্ডার এবং পোস্টঅর্ডার ট্রাভার্সাল সিকোয়েন্স আছে। আমাদের এই ক্রম থেকে গাছ তৈরি করতে হবে। তাই যদি পোস্টঅর্ডার এবং ইনঅর্ডার ক্রম [9,15,7,20,3] এবং [9,3,15,20,7] হয়, তাহলে গাছটি হবে −
আসুন ধাপগুলো দেখি -
- ধরুন পদ্ধতিটিকে প্রি-অর্ডার এবং ইনঅর্ডার তালিকা সহ বিল্ডট্রি বলা হয়
- root :=postorder থেকে শেষ নোড, এবং postorder থেকে প্রথম নোড মুছে দিন
- root_index :=ক্রম তালিকা থেকে root.val এর সূচক
- বাম বা রুট :=buildTree(root_index + 1 থেকে শেষ পর্যন্ত ইনঅর্ডারের উপসেট, পোস্টঅর্ডার)
- ডান বা রুট :=বিল্ড ট্রি (ইনডেক্স 0 থেকে রুট_ইনডেক্স, পোস্টঅর্ডারের সাবসেট)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def print_tree(root): #print using inorder traversal if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution(object): def buildTree(self, preorder, inorder): if inorder: root = TreeNode(preorder.pop(0)) root_index = inorder.index(root.data) root.left = self.buildTree(preorder,inorder[:root_index]) root.right = self.buildTree(preorder,inorder[root_index+1:]) return root ob1 = Solution() print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))
ইনপুট
[9,3,15,20,7] [9,15,7,20,3]
আউটপুট
9, 15, 7, 20, 3,
