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

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

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

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

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

উদাহরণ

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([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,