Path In Zigzag Labelled Binary Tree: หาเส้นทางใน Zigzag Tree

โจทย์

Infinite Binary Tree ที่ label แบบ Zigzag:

• Row คี่ (1,3,5...): Label ซ้าย→ขวา (ปกติ)
• Row คู่ (2,4,6...): Label ขวา→ซ้าย (กลับกัน)

กำหนด label ของโหนด หา path จาก root ไปยังโหนดนั้น

ตัวอย่าง: label=14 → path=[1,3,4,14]

Row 1: 1
Row 2: 3 2
Row 3: 4 5 6 7
Row 4: 15 14 13 12 11 10 9 8
...
Path to 14: 1 → 3 → 4 → 14

ข้อสังเกตสำคัญ: Mathematical Approach (O(log n))

แทนที่จะสร้าง tree (ใช้ memory มาก) ใช้คณิตศาสตร์:

• Row r มีโหนด 2^(r-1) ตัว
• Row r เริ่มที่ 2^(r-1) จบที่ 2^r - 1
• หา row ของ label
• หา "normal label" (ถ้าไม่ได้ zigzag) = label ถ้า row คี่, row_max + row_min - label ถ้า row คู่
• Parent ของ normal label = normal_label // 2
• แปลง parent กลับเป็น zigzag label ของ row ก่อนหน้า
• ทำซ้ำจนถึง root

การติดตั้ง (Python Implementation)

class Solution:
    def pathInZigZagTree(self, label: int) -> list[int]:
        # หา row ของ label
        row = 1
        while (1 << row) - 1 < label:
            row += 1
        
        path = []
        while label >= 1:
            path.append(label)
            
            # หา normal label (ใน standard binary tree)
            row_min = 1 << (row - 1)
            row_max = (1 << row) - 1
            if row % 2 == 0:  # even row: reversed
                normal_label = row_max + row_min - label
            else:
                normal_label = label
            
            # Parent ใน normal tree
            normal_parent = normal_label // 2
            if normal_parent == 0:
                break
            
            # แปลง parent กลับเป็น zigzag label
            row -= 1
            row_min = 1 << (row - 1)
            row_max = (1 << row) - 1
            if row % 2 == 0:
                label = row_max + row_min - normal_parent
            else:
                label = normal_parent
        
        return path[::-1]  # reverse เพื่อ root -> target

# ทดสอบ
ob = Solution()
print(ob.pathInZigZagTree(14))   # [1, 3, 4, 14]
print(ob.pathInZigZagTree(26))   # [1, 2, 6, 10, 26]
print(ob.pathInZigZagTree(1))    # [1]
print(ob.pathInZigZagTree(2))    # [1, 2]

Output

[1, 3, 4, 14]
[1, 2, 6, 10, 26]
[1]
[1, 2]

การวิเคราะห์ label=14

label=14
Row 4 (even): min=8, max=15, normal = 8+15-14 = 9
Parent normal = 9//2 = 4
Row 3 (odd): label = 4
Parent normal = 4//2 = 2
Row 2 (even): min=2, max=3, label = 2+3-2 = 3
Parent normal = 3//2 = 1
Row 1 (odd): label = 1
Path: [1, 3, 4, 14] ✓

Complexity

• Time: O(log label) - จำนวน row = log₂(label)
• Space: O(log label) - สำหรับ path output

สรุป

ใช้คณิตศาสตร์แปลงระหว่าง zigzag label และ normal binary tree label ไม่ต้องสร้าง tree จริง ทำได้ O(log n) time และ space

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ