पायथन में पोस्टऑर्डर और इनऑर्डर से बाइनरी ट्री बनाना

समस्या विवरण

बाइनरी ट्री का इनऑर्डर और पोस्टऑर्डर ट्रैवर्सल दिया गया है, ट्री पुनर्निर्मित करें।

उदाहरण

इनऑर्डर: [9, 3, 15, 20, 7]

पोस्टऑर्डर: [9, 15, 7, 20, 3]

आउटपुट (इनऑर्डर): 9, 3, 15, 20, 7

एल्गोरिदम (रिकर्सिव)

1. पोस्टऑर्डर का अंतिम तत्व रूट है
2. इनऑर्डर में रूट का इंडेक्स ind ढूंढें
3. बायां सबट्री: inorder[:ind], postorder (उपयुक्त भाग)
4. दायां सबट्री: inorder[ind+1:], postorder (उपयुक्त भाग)
5. रिकर्सिवली बनाएं

पायथन कार्यान्वयन

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:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def buildTree(self, inorder, postorder):
        if inorder:
            root = TreeNode(postorder.pop())
            ind = inorder.index(root.data)
            root.right = self.buildTree(inorder[ind+1:], postorder)
            root.left = self.buildTree(inorder[:ind], postorder)
            return root

ob1 = Solution()
print_tree(ob1.buildTree([9, 3, 15, 20, 7], [9, 15, 7, 20, 3]))

इनपुट

inorder=[9,3,15,20,7], postorder=[9,15,7,20,3]

आउटपुट

9, 3, 15, 20, 7