难度: Medium
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14 输出：[1,3,4,14]
示例 2：
输入：label = 26 输出：[1,2,6,10,26]
提示：
1 <= label <= 10^6运行时间: 23 ms
内存: 16.0 MB
class Solution:
def pathInZigZagTree(self, label: int) -> List[int]:
def get_range(depth):
return 2 ** depth, 2 ** (depth + 1) - 1
res = []
while label > 1:
res.append(label)
label = label // 2
abo_min, abo_max = get_range(int(log(label, 2)))
label = abo_max - (label - abo_min)
if label == 1:
res.append(label)
return res[::-1]
题解的核心思路是从给定的节点 label 开始向上回溯至根节点。在每个节点上进行操作时，需要考虑其所在行的顺序。偶数行节点的排列是从右到左的，而奇数行是从左到右。为了找到父节点，首先通过整除2得到父节点的标号。接着，为了得到正确的父节点标号，需要计算其在之字形排列中的实际位置。这通过计算当前行的范围，然后使用之字形转换公式（当前标号转换为正常二叉树中的对应位置）实现。该过程一直持续到到达根节点。最后，反转结果列表以得到从根节点到 label 的路径。
时间复杂度: O(log(label))
空间复杂度: O(log(label))
class Solution:
def pathInZigZagTree(self, label: int) -> List[int]:
def get_range(depth):
# 计算给定深度的最小和最大节点标号
return 2 ** depth, 2 ** (depth + 1) - 1
res = []
while label > 1:
# 将当前节点加入路径列表
res.append(label)
# 计算父节点的标号
label = label // 2
# 计算当前深度
depth = int(log(label, 2))
# 获取父节点层的范围
abo_min, abo_max = get_range(depth)
# 计算在之字形排列中的实际父节点标号
label = abo_max - (label - abo_min)
# 加入根节点
if label == 1:
res.append(label)
# 反转列表以得到从根节点到 label 的路径
return res[::-1]
这个公式用于计算之字形二叉树中父节点的实际标号。在之字形排列中，每一层的节点排列顺序会与上一层相反。因此，要找到实际的父节点位置，需要将父节点的标号映射到当前层的对应位置。公式中的 `label - abo_min` 计算出当前标号在其层中的相对位置，然后 `abo_max - (label - abo_min)` 通过从层的最大值减去这个相对位置，得到实际的父节点标号，反映了之字形排列的顺序。
是的，get_range 函数可以有效处理大数值。在 Python 中，整数类型可以处理非常大的数值，因为 Python 的整数类型是动态大小的。计算 2 的幂，即 `2 ** depth`，使用的是内置的幂运算符，该运算符针对大数值进行了优化。因此，即便是 label 达到 10^6 这样的大数值，get_range 函数也能准确并有效地计算出给定深度的最小和最大节点标号。
确实，使用浮点函数 `log` 计算可能会引入一些小的计算误差。为了确保计算得到正确的深度，可以使用 `math.log2` 函数代替 `log(label, 2)`，因为 `math.log2` 是专门设计来计算以 2 为底的对数，更精确。此外，使用 `int` 直接截断可能不安全，可以改用 `math.floor(math.log2(label))` 来确保总是向下取整，避免由于浮点误差导致的问题。
有其他方法可以避免最后的列表反转操作。一种方法是在生成路径时直接将节点插入到结果列表的前端。具体来说，可以使用列表的 `insert(0, label)` 方法将每个节点插入到列表的开始位置，这样生成的路径列表就已经是从根节点到 label 的正确顺序。虽然这种方法省去了反转操作，但频繁在列表首部插入元素的效率较低，因此对于大数据量的操作，使用反转方法可能更高效。