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

मान लीजिए एक अनंत बाइनरी ट्री में जहां प्रत्येक नोड के दो चिल्ड्रन हैं, नोड्स रो ऑर्डर में लेबल किए गए हैं। अब विषम नंबर वाली पंक्तियों (पहली, तीसरी, पांचवीं, ...) में, लेबलिंग बाएं से दाएं है, और सम नंबर वाली पंक्तियों (दूसरी, चौथी, छठी, ...) में, लेबलिंग दाएं से बाएं है। इसलिए ट्री इस तरह होगा -

इसलिए हमें इस ट्री में एक नोड का लेबल दिया गया है, हमें ट्री के रूट से उस लेबल वाले नोड तक के पथ में लेबल ढूंढने हैं। इसलिए यदि इनपुट label = 14 है, तो आउटपुट [1,3,4,14] होगा।

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

• दो ऐरे tree और res परिभाषित करें, tree ऐरे में 0 और 1 इन्सर्ट करें, odd := 1 और current := 1 और two := 2 सेट करें

• यदि label = 1, तो सिंगल एलिमेंट 1 वाली लिस्ट लौटाएं।

• एक अनंत लूप बनाएं -

  • यदि odd नॉन-जीरो है, तो

    • max_val := current + two

    • temp := max_val

    • जब तक temp > current

      • tree में temp इन्सर्ट करें

      • यदि temp = label, तो लूप से बाहर आएं

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

    • यदि tree का अंतिम एलिमेंट label है, तो लूप से बाहर आएं

    • current := max_val

  • अन्यथा

    • temp := two

    • जब तक temp शून्य नहीं है

      • temp := 1, current को 1 से बढ़ाएं, फिर current को tree में इन्सर्ट करें

      • यदि current = label, तो लूप से बाहर आएं

    • यदि tree का अंतिम एलिमेंट label है, तो लूप से बाहर आएं

  • temp := temp * 2

  • odd := false यदि odd नॉन-जीरो है, अन्यथा true

• index := tree की लंबाई - 1

• जब तक index 0 नहीं है

  • tree[index] को res ऐरे में इन्सर्ट करें

  • index := index / 2

• res := res की रिवर्स्ड लिस्ट

• res लौटाएं

उदाहरण (पायथन)

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

class Solution(object):
    def pathInZigZagTree(self, label):
        tree = []
        res = []
        tree.append(0)
        tree.append(1)
        odd = 1
        current = 1
        two = 2
        if label == 1:
            return [1]
        while True:
            if odd:
                max_val = current + two
                temp = max_val
                while temp>current:
                    tree.append(temp)
                    if temp == label:
                        break
                    temp-=1
                if tree[-1]== label:
                    break
                current = max_val
            else:
                temp = two
                while temp:
                    temp-=1
                    current+=1
                    tree.append(current)
                    if current == label:
                        break
                if tree[-1]== label:
                    break
            two*=2
            odd = not odd
        index = len(tree)-1
        while index:
            res.append(tree[index])
            index//=2
        res=res[::-1]
        return res

ob = Solution()
print(ob.pathInZigZagTree(14))

इनपुट

14

आउटपुट

[1,3,4,14]