পাইথনে পাথ ইন জিগজ্যাগ লেবেলযুক্ত বাইনারি ট্রি

ধরুন একটি অসীম বাইনারি ট্রিতে যেখানে প্রতিটি নোডের দুটি সন্তান রয়েছে, নোডগুলিকে সারি ক্রমে লেবেল করা হয়েছে৷ এখন বিজোড় সংখ্যাযুক্ত সারিগুলিতে (প্রথম, তৃতীয়, পঞ্চম,...), লেবেলিংটি বাম থেকে ডানে এবং জোড় সংখ্যাযুক্ত সারিতে (দ্বিতীয়, চতুর্থ, ষষ্ঠ,...), লেবেলিংটি ডান থেকে বামে রয়েছে . সুতরাং গাছটি −

তাই আমরা এই গাছে একটি নোডের লেবেল দিয়েছি, গাছের মূল থেকে নোড পর্যন্ত পথের লেবেলগুলো খুঁজে বের করতে হবে সেই লেবেল দিয়ে। সুতরাং ইনপুটটি যদি লেবেল =14 হয়, তাহলে আউটপুট হবে [1,3,4,14]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• দুটি অ্যারে ট্রি এবং রেস সংজ্ঞায়িত করুন, ট্রি অ্যারেতে 0 এবং 1 সন্নিবেশ করুন, বিজোড় সেট করুন :=1 এবং বর্তমান :=1 এবং দুই :=2

• যদি লেবেল =1, তাহলে একক উপাদান 1 সহ একটি তালিকা প্রদান করুন।

• একটি অসীম লুপ তৈরি করুন -

  • যদি বিজোড় অ-শূন্য হয়, তাহলে

    • max_val :=বর্তমান + দুই

    • তাপমাত্রা :=সর্বোচ্চ_ভাল

    • যখন temp> বর্তমান

      • গাছের মধ্যে তাপমাত্রা সন্নিবেশ করান

      • যদি temp =লেবেল, তাহলে লুপ থেকে বেরিয়ে আসুন

      • তাপমাত্রা 1 দ্বারা কমান

    • যদি গাছের শেষ উপাদান লেবেল হয়, তাহলে লুপ থেকে বেরিয়ে আসুন

    • বর্তমান :=সর্বোচ্চ_ভাল

  • অন্যথায়

    • তাপমাত্রা :=দুই

    • যখন তাপমাত্রা শূন্য নয়

      • temp :=1, কারেন্ট 1 দ্বারা বাড়ান, তারপর ট্রিতে কারেন্ট বাড়ান

      • যদি বর্তমান =লেবেল, তাহলে লুপ আকারে বেরিয়ে আসে

    • যদি গাছের শেষ উপাদান লেবেল হয়, তাহলে লুপ থেকে বেরিয়ে আসুন

  • temp :=temp * 2

  • বিজোড় :=বিজোড় যদি শূন্য না হয় তাহলে মিথ্যা, অন্যথায় সত্য

• সূচক :=গাছের দৈর্ঘ্য – 1

• যখন সূচক 0

  নয়

  • রেস অ্যারেতে ট্রি[ইনডেক্স] সন্নিবেশ করান

  • index :=index / 2

• 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]