---

1104. 二叉树寻路

• 标签：树、数学、二叉树
• 难度：中等

题目链接

• 1104. 二叉树寻路 - 力扣

题目大意

描述：在一棵无限的二叉树上，每个节点都有两个子节点。树的节点按"之"字形标记：

• 奇数行（第 $1$、$3$、$5$……行）：从左到右标记
• 偶数行（第 $2$、$4$、$6$……行）：从右到左标记

给定树上某个节点的标号 $label$。

要求：返回从根节点到该节点的路径（由途经的节点标号组成）。

说明：

• $1 \le label \le 10^6$。

示例：

• 示例 1：

输入：label = 14
输出：[1,3,4,14]

• 示例 2：

输入：label = 26
输出：[1,2,6,10,26]

解题思路

思路 1：数学 + 模拟

关键规律：

• 第 $k$ 层（从 $0$ 开始，根在第 $0$ 层）有 $2^k$ 个节点。

• 第 $k$ 层的编号范围是 $[2^k, 2^{k+1} - 1]$。

• 奇数层（$k$ 为偶数）从左到右，偶数层（$k$ 为奇数）从右到左。

• 正常顺序中的位置计算公式：$normal\_pos = 2^k + 2^{k+1} - 1 - label$

• 这个公式的意思是：把第 $k$ 层的左右反过来

拆解步骤：

1. 确定 $label$ 所在的层数：从第 $0$ 层开始累加节点数，直到覆盖 $label$。

2. 从 $label$ 向上回溯到根：

   • 如果当前在偶数层（之字形中的反向层），先把编号转成正常顺序
   • 正常顺序下，父节点编号 = 当前编号 $// 2$
   • 如果父节点在偶数层，再转回之字形编号
   • 记录路径

3. 反转路径得到从根到叶的顺序。

思路 1：代码

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        # 确定 label 在第几层（从第 0 层开始）
        level = 0
        while 2 ** (level + 1) <= label:
            level += 1

        path = []

        # 从 label 开始向上回溯到根
        while label >= 1:
            path.append(label)

            # 如果当前在偶数层（之字形中的反向层），需要转成正常顺序
            if level % 2 == 1:
                # 映射公式：对称翻转
                label = 2 ** level + 2 ** (level + 1) - 1 - label

            # 正常顺序下，父节点就是除以 2
            label //= 2
            level -= 1

            # 如果父节点在偶数层，转回之字形编号
            if label >= 1 and level % 2 == 1:
                label = 2 ** level + 2 ** (level + 1) - 1 - label

        # 从根到叶的顺序返回
        return path[::-1]

思路 1：复杂度分析

• 时间复杂度：$O(\log label)$。用人话说就是：二叉树的层数约为 $\log_2(label)$，每层只需要常数时间，所以时间和层数成正比。
• 空间复杂度：$O(\log label)$。路径长度等于层数，需要存储路径上所有节点。