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

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

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

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

• दो सरणी ट्री और रेस को परिभाषित करें, ट्री ऐरे में 0 और 1 डालें, विषम सेट करें:=1 और वर्तमान:=1 और दो:=2

• यदि लेबल =1 है, तो एकल तत्व 1 के साथ एक सूची लौटाएँ।

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

  • अगर विषम गैर-शून्य है, तो

    • max_val :=वर्तमान + दो

    • अस्थायी :=max_val

    • जबकि अस्थायी> वर्तमान

      • पेड़ में अस्थायी डालें

      • अगर अस्थायी =लेबल, तो लूप से बाहर आएं

      • तापमान में 1

        . की कमी करें

    • यदि पेड़ का अंतिम तत्व लेबल है, तो लूप से बाहर आएं

    • वर्तमान :=max_val

  • अन्यथा

    • अस्थायी:=दो

    • जबकि तापमान शून्य नहीं है

      • अस्थायी:=1, करंट को 1 से बढ़ाएँ, फिर करंट को ट्री में बढ़ाएँ

      • अगर करंट =लेबल है, तो लूप से बाहर आएं

    • यदि पेड़ का अंतिम तत्व लेबल है, तो लूप से बाहर आएं

  • अस्थायी:=अस्थायी * 2

  • विषम :=असत्य यदि विषम शून्य नहीं है, अन्यथा सत्य है

• सूचकांक :=पेड़ की लंबाई – 1

• जबकि इंडेक्स 0 नहीं है

  • ट्री [इंडेक्स] को रेस ऐरे में डालें

  • अनुक्रमणिका :=अनुक्रमणिका/2

• रेस :=रेस की उलटी सूची

• रिटर्न रेस

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

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

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]