मान लीजिए हमारे पास एक बाइनरी सर्च ट्री का पोस्टऑर्डर ट्रैवर्सल है; हमें उससे बाइनरी सर्च ट्री ढूंढना है।
यदि इनपुट [6, 12, 10, 55, 45, 15] जैसा है, तो आउटपुट होगा:
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- solve() नामक एक फंक्शन परिभाषित करें। यह postorder लेगा:
- n := postorder का आकार
- root := postorder के अंतिम तत्व के साथ एक नया ट्री नोड बनाएं
- stk := एक स्टैक
- root को stk में डालें
- i := n - 2
- जब तक i >= 0, करें:
- x := postorder[i] मान के साथ एक नया नोड बनाएं
- जब तक stk खाली नहीं है और postorder[i] < stk के शीर्ष का मान, करें:
- temp := stk का शीर्ष
- stk से शीर्ष तत्व हटाएं
- यदि temp null नहीं है, तो temp.left := x
- अन्यथा, stk के शीर्ष तत्व का राइट := x
- x को stk में डालें
- i := i - 1
- root लौटाएं
- मुख्य मेथड से निम्नलिखित करें:
- solve(postorder) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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 = []
stk.append(root)
i = n - 2
while i >= 0:
x = TreeNode(postorder[i])
temp = None
while len(stk) > 0 and postorder[i] < stk[-1].val:
temp = stk[-1]
stk.pop()
if temp != None:
temp.left = x
else:
stk[-1].right = x
stk.append(x)
i = i - 1
return root
def build_tree(postorder):
return solve(postorder)
def inord(node):
if node:
inord(node.left)
print(node.val, end = " ")
inord(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print("Inorder traversal:", end = " ")
inord(root)
इनपुट
[6, 12, 10, 55, 45, 15]
आउटपुट
6 10 12 15 45 55
