ধরুন আমাদের কাছে একটি বাইনারি ট্রির ইনঅর্ডার এবং প্রি-অর্ডার ট্রাভার্সাল সিকোয়েন্স আছে। আমাদের এই ক্রম থেকে গাছ তৈরি করতে হবে। সুতরাং যদি প্রি-অর্ডার এবং ইনঅর্ডার ক্রমগুলি [3,9,20,15,7] এবং [9,3,15,20,7] হয়, তাহলে গাছটি হবে −
আসুন ধাপগুলো দেখি -
- ধরুন পদ্ধতিটিকে প্রি-অর্ডার এবং ইনঅর্ডার তালিকা সহ বিল্ডট্রি বলা হয়
- root :=প্রি-অর্ডার থেকে প্রথম নোড, এবং প্রি-অর্ডার থেকে প্রথম নোড মুছে দিন
- root_index :=ক্রম তালিকা থেকে root.val এর সূচক
- বাম বা রুট :=বিল্ড ট্রি (প্রি-অর্ডার, ০ থেকে রুট_ইনডেক্স পর্যন্ত ইনঅর্ডারের উপসেট)
- ডান বা রুট :=buildTree(প্রি-অর্ডার, রুট_ইনডেক্স + 1 থেকে শেষ পর্যন্ত ইনঅর্ডারের উপসেট)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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([3,9,20,15,7], [9,3,15,20,7]))
ইনপুট
[3,9,20,15,7] [9,3,15,20,7]
আউটপুট
9, 3, 15, 20, 7,
