समस्या विवरण
बाइनरी सर्च ट्री का पोस्टऑर्डर ट्रैवर्सल दिया गया है, उससे BST पुनर्निर्मित करें।
उदाहरण
इनपुट: [6, 12, 10, 55, 45, 15]
आउटपुट: इनऑर्डर ट्रैवर्सल: 6 10 12 15 45 55
एल्गोरिदम (स्टैक-आधारित)
- अंतिम तत्व रूट है
- स्टैक में रूट डालें
- दाएं से बाएं (
n-2से 0) ट्रैवर्स करें:- नया नोड
xबनाएं - जब तक स्टैक खाली नहीं और
postorder[i] < stack[-1].val:temp = stack.pop()
- यदि
tempमौजूद:temp.left = x - अन्यथा:
stack[-1].right = x xको स्टैक में डालें
- नया नोड
- रूट वापस करें
पायथन कार्यान्वयन
class TreeNode:
def __init__(self, data=0):
self.val = data
self.left = None
self.right = None
def solve(postorder):
n = len(postorder)
root = TreeNode(postorder[n-1])
stk = [root]
i = n - 2
while i >= 0:
x = TreeNode(postorder[i])
temp = None
while stk and postorder[i] < stk[-1].val:
temp = stk.pop()
if temp:
temp.left = x
else:
stk[-1].right = x
stk.append(x)
i -= 1
return root
def inorder(node):
if node:
inorder(node.left)
print(node.val, end=' ')
inorder(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = solve(postorder)
print("Inorder traversal:", end=' ')
inorder(root)
इनपुट
[6, 12, 10, 55, 45, 15]
आउटपुट
6 10 12 15 45 55
