LeetCode 1104. 二叉树寻路
目录
题目描述
题意分析
有一棵无限深的完全二叉树，节点按「之字形」编号：最上面一行从左往右编号，下一行从右往左，再下一行又从左往右，如此交替。给定某个节点的编号
label，要求返回从根节点到它的完整路径上所有节点的编号。首先要把两套编号分清楚。如果按常规的「逐行从左到右」编号，节点的编号有一个极好的性质：父节点编号等于子节点编号除以 2。之字形编号破坏了这个性质，但只破坏在「奇数行被整体翻转」这一件事上——每一行包含的编号集合仍然是 $[2^L, 2^{L+1}-1]$，只是排列顺序反了。这个观察是全题的入口：编号集合没变，变的只是行内位置。
其次要意识到树是无限的，不能建出来。题目只给一个整数，答案长度等于层数，也就是 $O(\log label)$。这种「输入是一个数、输出是对数级长度的序列」的形态，几乎总是在暗示：直接用数学关系从下往上一步步推，而不是搜索。
还有一个方向问题：从根往下找目标需要在每层判断走左还是走右，反而麻烦；从
label往上回溯到根则每步只有唯一选择——父节点是确定的。所以自然的走向是自底向上，最后把序列反转。边界：
label = 1时路径就是根自己，答案是[1]；label上限 $10^6$，层数不超过 20，中间量远不会溢出int。
解法：从节点回溯到根
核心思路
从根向下需要判断每层走左还是走右；从目标向上时父节点唯一，因此选择自底向上回溯。
设当前节点标签为 $x$，位于第 $L$ 层（根为第 0 层）。这一层的标签范围为
\[[s,e]=[2^L,2^{L+1}-1]\]相邻两层的标号方向相反，由此可得到统一的父节点公式：
\[parent(x)=\left\lfloor\frac{s+e-x}{2}\right\rfloor\]这个公式不能简单解释成“每层都先把标签转换为普通编号”，因为偶数层本来就是正序。严谨地分两种情况验证：
- $L$ 为奇数时，当前层倒序。节点在普通完全二叉树中的编号是 $s+e-x$；父层为正序，所以除以 2 后就是父节点的之字形标签。
- $L$ 为偶数时，当前层正序，普通编号就是 $x$；父层倒序，其范围为 $[s/2,s-1]$。把普通父编号 $\lfloor x/2\rfloor$ 在父层镜像，得到 $(s/2+s-1)-\lfloor x/2\rfloor$，与上式相等。
因而无论当前层方向如何，都可以使用同一条转移。循环不变量是：每轮开始时，
label恰好是原目标到根路径上第level层的节点。记录它并按公式转移后，不变量在父层继续成立；到根再转移会得到 0，循环结束。最后反转自底向上的记录即可。
解题步骤
- 从
level = 0开始，持续检查2^(level+1) <= label，定位目标所在层。循环结束时满足 $2^{level}\le label<2^{level+1}$。- 将当前标签加入路径，计算本层左右端点
start = 1 << level、end = (start << 1) - 1。- 用
(start + end - label) / 2跳到父节点，同时令level--。Java 和 Go 的整数除法对非负数自动向下取整。- 重复到
label == 0，再反转路径。例如
label = 14：第 3 层区间为[8,15]，父节点是(8+15-14)/2=4；第 2 层区间为[4,7]，父节点是(4+7-4)/2=3；随后得到 1。回溯序列[14,4,3,1]反转后为[1,3,4,14]。边界
label = 1时，根先被记录，公式得到 0，最终直接返回[1]。
代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
public List<Integer> pathInZigZagTree(int label) {
int level = 0;
while ((1 << (level + 1)) <= label) {
level++;
}
List<Integer> path = new ArrayList<>();
while (label > 0) {
path.add(label);
int start = 1 << level;
int end = (start << 1) - 1;
label = (start + end - label) / 2;
level--;
}
Collections.reverse(path);
return path;
}
}
func pathInZigZagTree(label int) []int {
level := 0
for (1 << (level + 1)) <= label {
level++
}
path := make([]int, 0, level+1)
for label > 0 {
path = append(path, label)
start := 1 << level
end := (start << 1) - 1
label = (start + end - label) / 2
level--
}
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
return path
}
复杂度分析
- 时间复杂度：$O(\log label)$。定位层数、回溯和反转都只处理路径上的 $O(\log label)$ 个节点。
- 空间复杂度：$O(\log label)$ 用于返回路径；不计返回值时，额外空间为 $O(1)$。
关键点总结
- 每层标签的取值区间不变，只有排列方向改变；区间端点提供了镜像关系。
- 统一父节点公式是 $\lfloor(start+end-label)/2\rfloor$，它同时处理当前层和父层相反的编号方向。
- 正确性不依赖记忆公式：分别验证当前层正序、倒序两种情况即可覆盖所有层。
- 从目标回溯只有唯一父节点；末尾反转比反复头插更直接。
- 用整数位移定位层数，避免浮点对数在 2 的幂边界上产生精度问题。
易错点总结
- 直接用
label / 2求父节点。反例label = 14：会得到 7，而真实父节点是 4。- 只在倒序层应用镜像。反例路径经过
4时，第 2 层虽然正序，但它的父层倒序；4 / 2 = 2，正确父节点却是 3。- 层号多算一层。若写成
while ((1 << level) <= label) level++，label = 8会被误判到第 4 层；应比较下一层起点1 << (level + 1)。- 循环写成
label > 1会漏掉根；label = 1应返回[1]。- 忘记最终反转时，
label = 14会得到[14,4,3,1]，方向与题目要求相反。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 222. 完全二叉树的节点个数 | 中等 | 同样利用完全二叉树的编号规律，改为二分定位最后一层的节点位置 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 之字形出现在遍历输出顺序上而非编号上，用双端插入或逐层反转实现 |
| 662. 二叉树最大宽度 | 中等 | 给节点赋完全二叉树式的下标，靠同层首尾编号相减求宽度 |
| 919. 完全二叉树插入器 | 中等 | 由编号推父子关系用于动态插入，考察对完全二叉树结构的维护 |
| 1261. 在受污染的二叉树中查找元素 | 中等 | 由编号反推路径上的左右走向，是本题「自顶向下」方向的对照写法 |
| 958. 二叉树的完全性检验 | 中等 | 用编号连续性判断完全性，强化「完全二叉树编号即位置」这一核心认识 |