Path In Zigzag Labelled Binary Tree: Tìm Đường Đi Từ Root Đ Đến Node Trong Cây Zigzag

Đề bài: Cây nhị phân vô hạn, gán nhãn theo hàng (row). Hàng lẻ (1,3,5...): trái → phải. Hàng chẵn (2,4,6...): phải → trái. Cho nhãn label, tìm đường đi từ root (1) đến node đó.

Ví dụ: label=14 → [1,3,4,14].

Quan sát toán học

Cây nhị phân hoàn hảo: hàng level (1-indexed) có 2^(level-1) node, nhãn từ 2^(level-1) đến 2^level - 1.

Nếu không zigzag: parent của x là x//2.

Với zigzag: tại hàng chẵn, thứ tự đảo ngược. "Vị trí thực" (position từ trái) của nhãn label ở hàng level:

Hàng lẻ: pos = label - 2^(level-1)
Hàng chẵn: pos = (2^level - 1) - label

Parent ở hàng level-1 có position pos//2. Chuyển ngược lại nhãn parent.

Code Python (Tối ưu O(log n))


class Solution:
    def pathInZigZagTree(self, label: int) -> list[int]:
        # Tìm level của label
        level = label.bit_length()  # 2^(level-1) <= label < 2^level
        
        path = []
        while label >= 1:
            path.append(label)
            # Tính position tại level hiện tại
            level_start = 1 << (level - 1)        # 2^(level-1)
            level_end = (1 << level) - 1          # 2^level - 1
            
            if level % 2 == 0:  # Hàng chẵn: đảo ngược
                pos = level_end - label
            else:               # Hàng lẻ: thứ tự thường
                pos = label - level_start
            
            # Parent position
            parent_pos = pos // 2
            level -= 1
            
            # Chuyển parent_pos sang label ở level cha
            if level == 0:
                break
            parent_start = 1 << (level - 1)
            parent_end = (1 << level) - 1
            
            if level % 2 == 0:  # Parent ở hàng chẵn
                label = parent_end - parent_pos
            else:               # Parent ở hàng lẻ
                label = parent_start + parent_pos
        
        return path[::-1]  # Reverse để từ root đến label

# Test
ob = Solution()
print(ob.pathInZigZagTree(14))  # [1, 3, 4, 14]
print(ob.pathInZigZagTree(26))  # [1, 2, 6, 10, 26]

Giải thích test case `label=14`

14: binary 1110 → bit_length=4 → level 4 (hàng chẵn)
Level 4: start=8, end=15. pos = 15-14=1. parent_pos=0.
Level 3 (lẻ): start=4, end=7. label = 4+0=4.
Level 3: pos=4-4=0. parent_pos=0.
Level 2 (chẵn): start=2, end=3. label = 3-0=3.
Level 2: pos=3-3=0. parent_pos=0.
Level 1 (lẻ): start=1, end=1. label = 1+0=1.
Path: [1,3,4,14] ✓

Phân tích

Time: O(log label) (số level)
Space: O(log label) cho path
Không cần build tree, chỉ toán học bit.

Kết luận