पायथन में प्रीऑर्डर और पोस्टऑर्डर ट्रैवर्सल से बाइनरी ट्री निर्माण

मान लीजिए हमारे पास दो ट्रैवर्सल अनुक्रम प्रीऑर्डर और पोस्टऑर्डर हैं, हमें इन दो अनुक्रमों से बाइनरी ट्री उत्पन्न करना है। इसलिए यदि अनुक्रम [1,2,4,5,3,6,7], [4,5,2,6,7,3,1] हैं, तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ans := pre[0] मान लेकर एक ट्री नोड बनाएं, stack := खाली स्टैक, और ans डालें
• i := 1 और j := 0
• जबकि i < pre की लंबाई और j < post की लंबाई
  • यदि स्टैक शीर्ष मान = post[j], तो j को 1 से बढ़ाएं, स्टैक से पॉप करें, और अगले पुनरावृति के लिए जाएं
  • node := pre[i] मान के साथ एक ट्री नोड बनाएं
  • यदि स्टैक शीर्ष नोड का बायां भाग खाली है, तो स्टैक शीर्ष नोड के बाएं को node के रूप में सेट करें, अन्यथा स्टैक शीर्ष नोड के दाएं को node के रूप में सेट करें
  • node को स्टैक में डालें
  • i को 1 से बढ़ाएं
• ans लौटाएं

उदाहरण

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

def height(root):
    if root is None:
        return 0
    else:
        l_height = height(root.left)
        r_height = height(root.right)
        if l_height > r_height:
            return l_height + 1
        else:
            return r_height + 1

def print_given_level(root, level):
    if root is None:
        return
    if level == 1:
        print(root.data, end=',')
    elif level > 1:
        print_given_level(root.left, level-1)
        print_given_level(root.right, level-1)

def level_order(root):
    print('[', end='')
    h = height(root)
    for i in range(1, h+1):
        print_given_level(root, i)
    print(']')

class Solution(object):
    def constructFromPrePost(self, pre, post):
        ans = TreeNode(pre[0])
        stack = [ans]
        i = 1
        j = 0
        while i < len(pre) and j < len(post):
            if stack[-1].data == post[j]:
                j += 1
                stack.pop(-1)
                continue
            node = TreeNode(pre[i])
            if not stack[-1].left:
                stack[-1].left = node
            else:
                stack[-1].right = node
            stack.append(node)
            i += 1
        return ans

ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
level_order(tree)

इनपुट

[1,2,4,5,3,6,7] [4,5,2,6,7,3,1] pre = [1,2,4,5,3,6,7] post = [4,5,2,6,7,3,1]

आउटपुट

[1,2,3,4,5,6,7,]