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

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें जिगजैग लेवल ऑर्डर ट्रैवर्सल ढूंढना है। इसलिए पहली पंक्ति के लिए, बाएं से दाएं स्कैन करें, फिर दूसरी पंक्ति से दाएं से बाएं, फिर फिर से बाएं से दाएं और इसी तरह। इसलिए यदि ट्री इस तरह है -

ट्रैवर्सल क्रम [[3],[20,9],[15,7]] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यदि ट्री खाली है, तो खाली लिस्ट लौटाएं

• queue := एक क्यू बनाएं और रूट को क्यू में इन्सर्ट करें, दो खाली लिस्ट res और res2 बनाएं, और flag को True सेट करें

• जब तक क्यू खाली नहीं है

  • क्यू में मौजूद नोड्स की एक लिस्ट बनाएं, फिर res में इन्सर्ट करें

  • क्यू में मौजूद नोड मानों की एक लिस्ट बनाएं, फिर res2 में इन्सर्ट करें

  • यदि flag सेट है, तो

    • i := res में अंतिम सब-लिस्ट की लंबाई - 1

    • जब तक i >= 0

      • यदि res में अंतिम सब-लिस्ट का i-वां एलिमेंट का दायां सबट्री है, तो

        • दायां सबट्री को क्यू में इन्सर्ट करें

      • यदि res में अंतिम सब-लिस्ट का i-वां एलिमेंट का बायां सबट्री है, तो

        • बायां सबट्री को क्यू में इन्सर्ट करें

      • i को 1 से घटाएं

  • अन्यथा

    • i := res में अंतिम सब-लिस्ट की लंबाई - 1

    • जब तक i >= 0

      • यदि res में अंतिम सब-लिस्ट का i-वां एलिमेंट का दायां सबट्री है, तो

        • दायां सबट्री को क्यू में इन्सर्ट करें

      • यदि res में अंतिम सब-लिस्ट का i-वां एलिमेंट का बायां सबट्री है, तो

        • बायां सबट्री को क्यू में इन्सर्ट करें

      • i को 1 से घटाएं

• res2 लौटाएं

उदाहरण

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 zigzagLevelOrder(self, root):
        if not root:
            return []
        queue = [root]
        res = []
        res2=[]
        flag = True
        while len(queue)!=0:
            res.append([i for i in queue])
            res2.append([i.data for i in queue if i.data != 0])
            queue = []
            if flag:
                i=len(res[-1])-1
                while i>=0:
                    if res[-1][i].right:
                        queue.append(res[-1][i].right)
                    if res[-1][i].left:
                        queue.append(res[-1][i].left)
                    i-=1
            else:
                i=len(res[-1])-1
                while i>=0:
                    if res[-1][i].left:
                        queue.append(res[-1][i].left)
                    if res[-1][i].right:
                        queue.append(res[-1][i].right)
                    i-=1
                flag = not flag
        return res2

ob = Solution()
tree = make_tree([3,9,20,None,None,15,7])
print(ob.zigzagLevelOrder(tree))

इनपुट

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

आउटपुट

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