पायथन में बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल (Binary Tree Preorder Traversal)

मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें उस ट्री का प्रीऑर्डर ट्रैवर्सल लौटाना है। यदि ट्री इस तरह है:

तो प्रीऑर्डर ट्रैवर्सल होगा: [3,9,20,15,7]

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• res और st नामक दो खाली सूचियाँ बनाएं।
• node := root
• जब तक node या st खाली नहीं है:
  • जब तक node null नहीं है:
    • node का मान res में डालें, node को st में डालें और node := node का बायां बच्चा
  • temp := st का अंतिम तत्व, और st से अंतिम तत्व हटाएं
  • यदि temp का दायां बच्चा उपलब्ध है, तो:
    • node := temp का दायां बच्चा
• 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):
            temp.left = TreeNode(data)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            temp.right = TreeNode(data)
            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 preorderTraversal(self, root):
        res = []
        st = []
        node = root
        while node or st:
            while node:
                if node.data != None:
                    res.append(node.data)
                    st.append(node)
                node = node.left
            temp = st[-1]
            st.pop()
            if temp.right:
                node = temp.right
        return res

ob1 = Solution()
head = make_tree([3,9,20,None,None,15,7])
print(ob1.preorderTraversal(head))

इनपुट

[3,9,20,null,null,15,7]

आउटपुट

[3, 9, 20, 15, 7]