পাইথনে প্রिअর্ডার এবং ইনঅর্ডার ট্রাভার্সাল থেকে বাইনারি ট্রি কনস্ট্রাক্ট করা

মান করুন একটি বাইনারি ট্রির ইনঅর্ডার এবং প্রিঅর্ডার ট্রাভার্সাল সিকোয়েন্স দেওয়া আছে। আমাদের এই সিকোয়েন্স থেকে ট্রি জেনারেট করতে হবে। প্রিঅর্ডার এবং ইনঅর্ডার সিকোয়েন্স যথাক্রমে [3,9,20,15,7] এবং [9,3,15,20,7] হলে ট্রিটি হবে নিচের মতো:

ধাপগুলো নিচে দেওয়া হলো:

মেথডের নাম buildTree ধরে নিলে প্রিঅর্ডার এবং ইনঅর্ডার লিস্ট দিয়ে
root := প্রিঅর্ডার থেকে প্রথম নোড, এবং প্রিঅর্ডার থেকে প্রথম নোড ডিলিট করুন
root_index := ইনঅর্ডার লিস্ট থেকে root.val-এর ইনডেক্স
root.left := buildTree(প্রিঅর্ডার, ইনঅর্ডারের সাবসেট ০ থেকে root_index)
root.right := buildTree(প্রিঅর্ডার, ইনঅর্ডারের সাবসেট root_index+1 থেকে শেষ)

নিচে ইমপ্লিমেন্টেশন দেওয়া হলো:

উদাহরণ

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_tree(root):
    # ইনঅর্ডার ট্রাভার্সাল দিয়ে প্রিন্ট
    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,