题目描述
思路解析动画文字版
记牢两步:先翻倍定行,再「镜像加折半」逐行爬到父节点。镜像 = 本行最小加最大减自己,目的就是抵消之字形的方向翻转。下面每一帧都在套这套规则。
总览 · 之字形编号树：先看清这棵树长什么样。树是无限大的,这里只画出和我们这次寻路有关的一小块。每个圆圈里的数字就是这个节点的标号,注意行与行之间,编号方向是反复掉头的。
第 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题