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

समस्या विवरण

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

उदाहरण

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

इनऑर्डर (सॉर्टेड): [3, 7, 9, 15, 20]

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

एल्गोरिदम

1. inorder = sorted(postorder)
2. सामान्य बाइनरी ट्री निर्माण (पिछले आर्टिकल जैसा)

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

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()
postorder = [3, 9, 20, 15, 7]
inorder = sorted([3, 9, 20, 15, 7])
print_tree(ob1.buildTree(inorder, postorder))

इनपुट

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

आउटपुट

3, 7, 9, 15, 20