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

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इस ट्री का पोस्टऑर्डर ट्रैवर्सल पुनरावृत्त दृष्टिकोण का उपयोग करके ढूंढना है। यदि ट्री इस तरह है:

तो आउटपुट होगा: [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]