题目重点：用子树大小定位 preorder 编号，分别找根到两点路径并在 LCA 拼接，时间空间都随阶数增长。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- F(0) 与 F(1) 各一结点；k≥2 时根的左子树 F(k−2)、右子树 F(k−1)，前序编号从 0 连续递增；a,b 为有效节点 ID。
- 输出从 a 到 b 的节点编号序列，包含端点和最近公共祖先一次。题目说‘输出节点序列/思路即可’，具体函数签名为训练实现。
解题路线
- 预计算 size[0]=size[1]=1，size[k]=1+size[k−2]+size[k−1]；不能仅说‘任意二叉树都有 size(left)+size(right)+1’，关键是阶数决定子树大小，因此不用建节点。
- 当前 F(k) 根编号 r 时，左根 r+1，其区间长 size[k−2]；右根 r+1+size[k−2]，区间长 size[k−1]。比较 target 与区间边界，迭代进入左/右，同时保存根 ID。
- 分别求 root→a、root→b 路径，找到最长公共前缀；其最后节点就是 LCA。将 a 路径的非公共后缀逆序、LCA、b 路径的非公共后缀拼接。
- k 很大时 size 可能超固定宽整数；Python 用大整数，C++ 需检查溢出或在仅定位给定 target 时做有上界的饱和比较。不能把 pre-order 标签误作节点值相加。
手动走一遍
F(3) 的左是 F(1) 单点、右是 F(2) 三点；前序编号根 0、左 1、右子树根 2，其左 3、右 4。a=1,b=4 时路径为 1→0→2→4，公共前缀仅根 0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""F(k): F(0), F(1) each one node; F(k) has left F(k-2), right F(k-1).
Nodes are labeled from zero in preorder. Find the sequence from a to b
without materializing the tree, using the stated child orientation.
"""
def sizes_up_to(order: int) -> list[int]:
if order < 0:
raise ValueError('order must be nonnegative')
sizes = [1] * (order + 1)
for level in range(2, order + 1):
sizes[level] = 1 + sizes[level - 2] + sizes[level - 1]
return sizes
def path_from_root(order: int, target: int, sizes: list[int]) -> list[int]:
if not 0 <= target < sizes[order]:
raise ValueError('target outside tree')
root, level = 0, order
path = []
while True:
path.append(root)
if root == target:
return path
if level < 2:
raise AssertionError('unreachable target')
left_root = root + 1
left_end = left_root + sizes[level - 2]
if target < left_end:
root, level = left_root, level - 2
else:
root, level = left_end, level - 1
def path_between(order: int, a: int, b: int) -> list[int]:
sizes = sizes_up_to(order)
left = path_from_root(order, a, sizes)
right = path_from_root(order, b, sizes)
common = 0
while common < min(len(left), len(right)) and left[common] == right[common]:
common += 1
return list(reversed(left[common:])) + [left[common - 1]] + right[common:]
复杂度
size 表 O(k) 时间/O(k) 空间；每个 root→target 路径长度至多 O(k)，拼接 O(k)，总 O(k) 时间/O(k) 空间。显式建树需要与节点总数同阶的时间和内存，随 k 近指数增长。
易错点与追问
容易失分的边界
- Fibonacci 指子树阶数/大小，不是节点值。
- 左右 F(k−2)/F(k−1) 互换会改变 preorder 标签。
- 右子树根忘加整个左子树大小。
- 拼接时 LCA 重复或端点遗漏。
- 固定宽整数 size 溢出。
继续深挖
- 只需 a 与 b 距离而不输出路径，能否降低空间？
- 编号从 1 开始怎么改边界？
- k 过大时如何避免溢出？
- 若左右阶数互换，为什么节点总数一样但答案不同？
