मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इस ट्री का पोस्टऑर्डर ट्रैवर्सल पुनरावृत्त दृष्टिकोण का उपयोग करके ढूंढना है। इसलिए यदि ट्री इस तरह है −
तो आउटपुट होगा: [9,15,7,10,-10]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
यदि रूट null है, तो खाली सरणी लौटाएं
एक सरणी ret बनाएं
stack := जोड़ी [root, 0] के साथ एक स्टैक परिभाषित करें
जब तक स्टैक खाली नहीं है −
node := स्टैक का शीर्ष, फिर स्टैक से तत्व हटाएं।
यदि नोड जोड़ी का दूसरा मान 0 है, तो
current := नोड जोड़ी का पहला मान
स्टैक में जोड़ी (current, 1) डालें
यदि current का दायां मौजूद है −
स्टैक में जोड़ी [current का दायां, 0] डालें
यदि current का बायां मौजूद है −
स्टैक में जोड़ी [current का बायां, 0] डालें
अन्यथा जब नोड जोड़ी के पहले मान का डेटा 0 नहीं है, तो नोड जोड़ी के पहले मान के डेटा को res में डालें
res लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def postorderTraversal(self, root): if not root: return [] res = [] stack = [[root,0]] while stack: node = stack[-1] stack.pop() if node[1]== 0 : current = node[0] stack.append([current,1]) if current.right: stack.append([current.right,0]) if current.left: stack.append([current.left,0]) else: if node[0].data != 0: res.append(node[0].data) return res ob = Solution() root = make_tree([-10,9,10,None,None,15,7]) print(ob.postorderTraversal(root))
इनपुट
[-10,9,10,None,None,15,7]
आउटपुट
[9, 15, 7, 10, -10]
