ধরুন একটি অসীম বাইনারি ট্রিতে যেখানে প্রতিটি নোডের দুটি সন্তান রয়েছে, নোডগুলিকে সারি ক্রমে লেবেল করা হয়েছে৷ এখন বিজোড় সংখ্যাযুক্ত সারিগুলিতে (প্রথম, তৃতীয়, পঞ্চম,...), লেবেলিংটি বাম থেকে ডানে এবং জোড় সংখ্যাযুক্ত সারিতে (দ্বিতীয়, চতুর্থ, ষষ্ঠ,...), লেবেলিংটি ডান থেকে বামে রয়েছে . সুতরাং গাছটি −
এর মত হবে
তাই আমরা এই গাছে একটি নোডের লেবেল দিয়েছি, গাছের মূল থেকে নোড পর্যন্ত পথের লেবেলগুলো খুঁজে বের করতে হবে সেই লেবেল দিয়ে। সুতরাং ইনপুটটি যদি লেবেল =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]