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

মনে করুন একটি অনন্ত বাইনারি ট্রি যেখানে প্রতিটি নোডের দুটি চাইল্ড আছে, নোডগুলো রো-অর্ডারে লেবেল করা হয়েছে। এখন বিজোড় নম্বরवाले রোগুলোতে (প্রথম, তৃতীয়, পঞ্চম...), লেবেলিং লেফট-টু-রাইট, এবং জোড় নম্বরवाले রোগুলোতে (দ্বিতীয়, চতুর্থ, ষষ্ঠ...), লেবেলিং রাইট-টু-লেফট। তাই ট্রিটি হবে নিচের মতো:

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

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব:

tree এবং res দুটি অ্যারে, tree-এ ০ এবং ১ ইনসার্ট করুন, odd := 1, current := 1, two := 2 সেট করুন।
যদি label == 1, তবে [1] রিটার্ন করুন।
একটি ইনফিনিট লুপ:
- যদি odd true হয়:
  - max_val := current + two
  - temp := max_val
  - while temp > current:
    - tree.append(temp)
    - যদি temp == label, তবে লুপ ব্রেক করুন।
    - temp -= 1
  - যদি tree[-1] == label, তবে ব্রেক করুন।
  - current := max_val
- অন্যথায় (ইভেন রো):
  - temp := two
  - while temp != 0:
    - temp -= 1, current += 1, tree.append(current)
    - যদি current == label, তবে ব্রেক করুন।
  - যদি tree[-1] == label, তবে ব্রেক করুন।
- two *= 2
- odd := not odd
index := len(tree) - 1
while index != 0:
- res.append(tree[index])
- index //= 2
res := reversed(res)
return res

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

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))

ইনপুট

আউটপুট

[1, 3, 4, 14]