题目描述
思路解析
一句话答案：LeetCode 1104 二叉树寻路：满二叉树按之字形逐行编号，给 label 求根到它的路径。先翻倍定行，再逐行「镜像加折半」抵消偶数行的翻转爬到父节点，时间 O(log label)。
题目给一个标号，要哪条路径
有一棵无限大的满二叉树，也就是每层都填满节点的二叉树，标号自上而下一行行贴。第 i 行有 2 的 (i-1) 次方个节点，占满 2 的 (i-1) 次方 到 2 的 i 次方减 1。奇数行从左往右贴、偶数行从右往左贴，来回掉头，这就是之字形。给你标号 label，把根到它路上的标号从上到下列出来。题面 label=14 答案 [1,3,4,14]，label=26 答案 [1,2,6,10,26]。
直接除以 2 找父节点，为什么爬岔了
普通满二叉树里父亲就是自己除以 2，一路除到 1 就是路径。可这棵树偶数行被从右往左翻转过，排布变了。拿 14 试：除以 2 是 7，但 7 在第 3 行，14 真正的父亲是 4，一除就爬岔了。把无限树建出来再找也不行，标号能到几十亿。
偶数行的翻转，靠一次镜像抵消
盯住相邻两行：编号方向永远相反，一个从左往右、下一个从右往左，正是这个相反让直接除以 2 失灵。补救是先在本行做镜像：镜像 = 本行最小标号 加 本行最大标号 减自己。第 i 行范围是 2 的 (i-1) 次方 到 2 的 i 次方减 1，镜像后的值方向已和父节点那行对齐，这时再除以 2，就落到父节点的真实标号。
先翻倍定行，再逐行往上爬
过程分先后两段。定行：让 x 和 i 都从 1 起步，x 是第 i 行的最小标号，不停把 x 翻倍、i 加一，直到再翻一倍就超过 label，此时的 i 就是 label 所在行。上爬：从这行起，每行镜像加折半得到父标号、收进答案、行号减一，直到爬回根。Python 用 ans[i-1] 从后往前填正好是根到 label 顺序；C++、Java 顺着收集则末尾要 reverse。
label=14，四行怎么一步步爬回根
先定行。x 从 1 出发翻倍：2、4、8，行号 i 数到 4；下一次翻倍是 16，超过 14，停。14 在第 4 行，答案 4 个标号。
从第 4 行的 14 往上。第 4 行范围 8 到 15，镜像 8+15-14=9，除以 2 得 4，是 14 的父亲。第 3 行范围 4 到 7，镜像 4+7-4=7，得 3。第 2 行范围 2 到 3，镜像 2+3-3=2，得 1。第 1 行是根 1。自底向上收到 14、4、3、1，倒过来就是 [1,3,4,14]，和题面一致。
只走行号那么多步，剩三处要盯牢
复杂度：label 的行号约是以 2 为底 label 的对数。定行和上爬各走行号那么多步，时间 O(log label)；路径长度就等于行号，是结果占的空间，额外只用常数个变量。
三处细节得盯牢。忘了镜像、直接拿 label 除以 2，会爬到翻转前的错标号，像 14 会错成 7。把第 i 行范围记成 2 的 i 次方 开头，最小最大全偏一位、镜像跟着全错，范围应是 2 的 (i-1) 次方 到 2 的 i 次方减 1。收集顺序也别忘：C++、Java 漏了 reverse 就头尾颠倒。边界上根标号 1 单独成路；第 2 行的 2 在最右，先镜像成 3 再除以 2 回到根 1。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢两步:先翻倍定行,再「镜像加折半」逐行爬到父节点。镜像 = 本行最小加最大减自己,目的就是抵消之字形的方向翻转。下面每一帧都在套这套规则。
总览 · 之字形编号树：先看清这棵树长什么样。树是无限大的,这里只画出和我们这次寻路有关的一小块。每个圆圈里的数字就是这个节点的标号,注意行与行之间,编号方向是反复掉头的。
第 1 行 · 根：最上面第 1 行,只有一个根节点,标号就是 1。它的范围是 2 的 0 次方 到 2 的 1 次方减 1,也就是只有 1 这一个数。第 1 行算奇数行,从左到右编。
第 2 行 · 被翻转：第 2 行有两个节点,标号占 2 和 3。可它是偶数行,要从右往左编号,于是右边那个反而是 2、左边那个是 3。看清楚了吗,这一行被掉了个头,这正是之字形最容易绕晕的地方。
第 3 行 · 正序：第 3 行是奇数行,又回到从左往右,标号规规矩矩是 4、5、6、7。可以看到方向又掉回来了,和第 2 行正好相反。
第 4 行 · 又翻转：第 4 行又是偶数行,再次从右往左,整行应该是 15、14、13 一直到 8。屏幕地方有限,只画出靠左的 15 和 14 两个,它们正是节点 4 的两个孩子。我们要找的 14 就藏在这一行里。
定行 · 从 1 起步：开始定位 14 在第几行。从 x 等于 1、i 等于 1 出发,x 始终代表第 i 行标号范围的起点、也就是这一行的最小标号 2 的 (i-1) 次方(注意之字形里偶数行被翻转,屏幕上最左端那个未必是它)。试着翻倍:1 乘 2 等于 2,2 还小于等于 14,说明 14 在更下面,往下走一行。
定行 · 翻到第 2 行：x 翻成 2,i 变成 2,现在停在第 2 行。再翻倍:2 乘 2 等于 4,4 仍然小于等于 14,14 还在更深处,接着往下。
定行 · 翻到第 3 行：x 翻成 4,i 变成 3。再翻倍:4 乘 2 等于 8,8 还是小于等于 14,14 依旧在下面,再下一行看看。
定行 · 停在第 4 行：x 翻成 8,i 变成 4。这回再翻倍是 16,16 已经大于 14 了,不能再往下,停手。于是确定 14 就落在第 4 行,这一行标号范围是 8 到 15。
定行完成 · 14 在第 4 行：行号定下来了,14 在第 4 行。因为它在第 4 行,从根到它一共要经过 4 个节点,所以答案会是 4 个标号。接下来从 14 出发,一行一行往上爬到根。
第 4 行 · 看 14：现在处理标号 14,它在第 4 行,这一行的标号范围是 8 到 15。普通满二叉树里父节点就是自己除以 2,但偶数行被翻转过,直接除不是可靠通用规则,这里统一先镜像再折半。
第 4 行 · 镜像 14：做镜像:把本行的最小 8 加最大 15,再减掉自己 14,得到 9。这个 9 就是 14 在本行里左右对称的那个位置。镜像这一下,正好抵消了相邻两行方向相反带来的错位。
第 4 行 ➜ 第 3 行 · 折半：把镜像值 9 除以 2,向下取整得到 4。神奇的地方在这里:因为上一行的编号方向和这一行正好相反,镜像加折半两步一合,4 不是别的中间量,它就是 14 父节点的真实标号。把 4 记下来,继续往上爬。
第 3 行 · 看 4：现在处理标号 4,它在第 3 行,这一行的标号范围是 4 到 7。普通满二叉树里父节点就是自己除以 2,但偶数行被翻转过,直接除不是可靠通用规则,这里统一先镜像再折半。
第 3 行 · 镜像 4：做镜像:把本行的最小 4 加最大 7,再减掉自己 4,得到 7。这个 7 就是 4 在本行里左右对称的那个位置。镜像这一下,正好抵消了相邻两行方向相反带来的错位。
第 3 行 ➜ 第 2 行 · 折半：把镜像值 7 除以 2,向下取整得到 3。神奇的地方在这里:因为上一行的编号方向和这一行正好相反,镜像加折半两步一合,3 不是别的中间量,它就是 4 父节点的真实标号。把 3 记下来,继续往上爬。
第 2 行 · 看 3：现在处理标号 3,它在第 2 行,这一行的标号范围是 2 到 3。普通满二叉树里父节点就是自己除以 2,但偶数行被翻转过,直接除不是可靠通用规则,这里统一先镜像再折半。
第 2 行 · 镜像 3：做镜像:把本行的最小 2 加最大 3,再减掉自己 3,得到 2。这个 2 就是 3 在本行里左右对称的那个位置。镜像这一下,正好抵消了相邻两行方向相反带来的错位。
第 2 行 ➜ 第 1 行 · 折半：把镜像值 2 除以 2,向下取整得到 1。神奇的地方在这里:因为上一行的编号方向和这一行正好相反,镜像加折半两步一合,1 不是别的中间量,它就是 3 父节点的真实标号。把 1 记下来,继续往上爬。
到达根 · 第 1 行：爬到第 1 行了,当前标号是 1,也就是根。根没有父节点,上爬到此结束。一路自底向上收集到的标号是 14、4、3、1,马上把它倒过来就是答案。
总装 · 倒序拼路径：上爬是从底往上收的,顺序是 14、4、3、1。题目要的是从根到 14 自上而下的顺序,所以把它倒过来,得到 1、3、4、14。
完成 · 路径成形：紫色这条链就是从根到 14 的路:1 到 3 到 4 到 14,答案 [1,3,4,14]。回顾一下,我们压根没有真的把这棵无限树建出来,只靠翻倍定行、再镜像折半逐行上爬,几步就把路径算了出来。
边界先想清:根单独成路;第 2 行 2 在右,先镜像成 3,再除以 2 回到根 1;第 3 行最右的 7 镜像折半爬到 2 再到 1。
面试重点:镜像抵消相邻行的方向翻转所以落到真实父节点、行号约 log label 所以对数级、必须先定行才能算镜像。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def pathInZigZagTree(self, label: int) -> List[int]: x = i = 1 while (x << 1) <= label: x <<= 1 i += 1 ans = [0] * i while i: ans[i - 1] = label label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1 i -= 1 return ans复杂度
- 时间：O(log label)，行号约等于以 2 为底 label 的对数。先翻倍定行走 O(log label) 次,再逐行上爬同样 O(log label) 次,合起来还是对数级
- 空间：O(log label)，要返回的路径长度等于行号,约 log label;这是结果本身占的空间。除答案外只用了几个整数变量,额外空间 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么镜像再除以 2 得到的就是父节点的真实标号,而不是某个中间值?
追问复杂度为什么是对数级而不是线性?
追问可以不先定行、直接往上爬吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删点成林
LeetCode 1110 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题