教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文是「宫水三叶的刷题日记」刷穿 LeetCode 系列第 1104 篇题解的深度展开对应仓库文件 LeetCode/1101-1110/1104. 二叉树寻路中等.md。文章围绕一棵按「之」字形Zigzag标记的无限满二叉树系统讲解「从任意节点回溯到根节点」的两类解法朴素的逐层模拟回溯以及基于层内对称性、复杂度为 O(log n) 的数学寻址。读完本文你将掌握满二叉树「层级 → 起始值/结束值」的 O(1) 计算模型、之字形翻转对父子关系的破坏方式以及如何用一条对称性公式在任意层间 O(1) 定位父节点并能在 Java / C / Python 中直接落地运行。题目描述与关键信息在 LeetCode 第 1104 题中给定一棵无限满二叉树每个节点都有两个子节点且每一层都是满的节点标号逐行按「之」字形Zigzag进行奇数行第 1、3、5 … 行按从左到右的顺序标记偶数行第 2、4、6 … 行按从右到左的顺序标记。题意即给定树上某一个节点的标号label返回从根节点到该节点的路径路径由途经节点的标号组成含根节点与自身。两个示例输入label 14 输出[1,3,4,14] 输入label 26 输出[1,2,6,10,26]约束条件1 label 10^6。本题 Tag 为「二叉树」「模拟」「数学」推荐指数在仓库的 Index/二叉树.md 索引中被标记为 。它的难点不在树的遍历本身而在于之字形翻转使「父节点 子节点 / 2」这一满二叉树基本性质失效——你需要重新建立一套受奇偶层影响的父子寻址规则。核心模型满二叉树的层级结构解题的第一步是建立「层级」与「节点值区间」的映射。因为树每一层都是满的所以第level层level从 1 开始计数共有2^(level-1)个节点该层节点值的范围是[2^(level-1), 2^level - 1]。这一结论可以直接推导前level-1层共2^(level-1) - 1个节点因此第level层从2^(level-1)开始到2^level - 1结束。对应到代码中就是两个 O(1) 辅助函数// 第 level 层的起始节点值 int getStart(int level) { return (int)Math.pow(2, level - 1); } // 第 level 层的结束节点值 int getEnd(int level) { int a getStart(level); return a a - 1; // 即 2^level - 1 }借助getEnd(level)可以确定任意label所在的层级int level 1; while (getEnd(level) label) level;由于label 10^6而2^19 524288、2^20 1048576因此最大层级不超过 20从任意节点到根的路径长度至多 20 个节点。这也是后续所有解法的规模前提。有了「起始值 结束值」再结合「每层节点数量翻倍」与「隔层奇偶性翻转」就可以自底向上回溯父节点了。解法一模拟朴素逐层回溯思路一个朴素而直观的做法是完全按照题意模拟先确定label所在层级level并计算出该层起始值start与结束值end从当前节点cur出发根据level的奇偶性判断该层节点的数值递增方向偶数层该层「从右往左」数值递增因此向上寻址时也应「从右往左」计算上一层下标奇数层该层「从左往右」数值递增向上寻址时也应「从左往右」计算上一层下标。令每层下标均「从左往右」计算、并从 1 开始在层内线性定位cur的下标j再换算到上一层对应下标的节点值得到父节点重复直到寻址到根节点将沿途节点值填入答案数组。实现时答案数组按level大小开好从后往前自底向上填充即可得到「根 → label」的顺序。复杂度时间复杂度确定label所在层级为 O(log n)构造答案时最坏情况下层内每个节点会被线性遍历一次整体为 O(n)空间复杂度O(1)不含返回答案所需的数组。Java 代码class Solution { // 第 level 层的起始节点值 int getStart(int level) { return (int)Math.pow(2, level - 1); } // 第 level 层的结束节点值 int getEnd(int level) { int a getStart(level); return a a - 1; } public ListInteger pathInZigZagTree(int n) { // 计算 n 所在层级 int level 1; while (getEnd(level) n) level; int[] ans new int[level]; int idx level - 1, cur n; while (idx 0) { ans[idx--] cur; int tot (int)Math.pow(2, level - 1); int start getStart(level), end getEnd(level); if (level % 2 0) { // 当前层为偶数层则当前层节点「从右往左」数值递增相应计算上一层下标也应该「从右往左」 int j tot / 2; for (int i start; i end; i 2, j--) { if (i cur || (i 1) cur) break; } int prevStart getStart(level - 1); while (j-- 1) prevStart; cur prevStart; } else { // 当前层为奇数层则当前层节点「从左往右」数值递增相应计算上一层下标也应该「从左往右」 int j 1; for (int i start; i end; i 2, j) { if (i cur || (i 1) cur) break; } int prevEnd getEnd(level - 1); while (j-- 1) prevEnd--; cur prevEnd; } level--; } ListInteger list new ArrayList(); for (int i : ans) list.add(i); return list; } }C 代码class Solution { public: int getStart(int level) { return (int)pow(2, level - 1); } int getEnd(int level) { int a getStart(level); return a a - 1; } vectorint pathInZigZagTree(int n) { int level 1; while (getEnd(level) n) level; vectorint ans(level); int idx level - 1, cur n; while (idx 0) { ans[idx--] cur; int tot (int)pow(2, level - 1); int start getStart(level), end getEnd(level); if (level % 2 0) { int j tot / 2; for (int i start; i end; i 2, j--) { if (i cur || (i 1) cur) break; } int prevStart getStart(level - 1); while (j-- 1) prevStart; cur prevStart; } else { int j 1; for (int i start; i end; i 2, j) { if (i cur || (i 1) cur) break; } int prevEnd getEnd(level - 1); while (j-- 1) prevEnd--; cur prevEnd; } level--; } return ans; } };Python 代码class Solution: def pathInZigZagTree(self, n: int) - List[int]: def get_start(level): return 2 ** (level - 1) def get_end(level): a get_start(level) return a a - 1 level 1 while get_end(level) n: level 1 ans [0] * level idx, cur level - 1, n while idx 0: ans[idx] cur idx - 1 tot 2 ** (level - 1) start, end get_start(level), get_end(level) if level % 2 0: j tot // 2 for i in range(start, end 1, 2): if i cur or (i 1) cur: break j - 1 prev_start get_start(level - 1) while j 1: prev_start 1 j - 1 cur prev_start else: j 1 for i in range(start, end 1, 2): if i cur or (i 1) cur: break j 1 prev_end get_end(level - 1) while j 1: prev_end - 1 j - 1 cur prev_end level - 1 return ans模拟解法可用示例 1 手工验证label 14位于第 4 层偶数层层内数值从右往左递增14 在该层的下标为 1从左往右数换算到第 3 层的父节点为 4第 3 层奇数层中 4 的下标为 1换算到第 2 层的父节点为 3第 2 层偶数层中 3 的下标为 1父节点为 1最终得到[1,3,4,14]。解法二数学O(log n) 对称性寻址思路模拟解法的复杂度上界来自「由当前行节点位置确定上层位置」时的层内线性遍历。如果二叉树不具有奇偶性翻转那么任意节点x的父节点显然是⌊x / 2⌋但之字形翻转破坏了这条性质。不过解法一中已经能 O(1) 计算任意一层的起始值与结束值。有了「起始值 结束值」和「当前节点所在层的相对位置」只需利用对称性找到父节点在上层的相应位置再根据相应位置算出父节点值即可——从而把单步回溯从 O(层宽) 降到 O(1)。具体地设当前节点为cur、所在层为level层level的节点值区间为[2^(level-1), 2^level - 1]因此2^level - 1 - cur恰好是cur距离该层右端数值最大值端的距离即其在层内的「镜像偏移量」由于满二叉树中父节点位置 子节点位置 / 2位置按从左到右、0 起始计把该偏移量右移一位 1等价于整除 2即可得到父节点在上一层内的偏移loc上一层level - 1的起始值为2^(level-2)于是父节点值 2^(level-2) loc。合并成一条核心公式loc ((1 level) - 1 - cur) 1 cur (1 (level - 2)) loc这条公式对奇偶层统一成立奇数层本身从左往右递增偶数层是从右往左递增的镜像层而「先取层内镜像偏移、再右移定位上层位置」恰好同时处理了这两种方向无需分支判断。这也是数学解法代码比模拟解法更短的原因。复杂度时间复杂度上界取决于确定label所在层级的循环为 O(log n)空间复杂度O(1)。Java 代码class Solution { int getStart(int level) { return (int)Math.pow(2, level - 1); } int getEnd(int level) { int a getStart(level); return a a - 1; } public ListInteger pathInZigZagTree(int n) { int level 1; while (getEnd(level) n) level; int[] ans new int[level]; int idx level - 1, cur n; while (idx 0) { ans[idx--] cur; int loc ((1 (level)) - 1 - cur) 1; cur (1 (level - 2)) loc; level--; } ListInteger list new ArrayList(); for (int i : ans) list.add(i); return list; } }C 代码class Solution { public: int getStart(int level) { return pow(2, level - 1); } int getEnd(int level) { int a getStart(level); return a a - 1; } vectorint pathInZigZagTree(int n) { int level 1; while (getEnd(level) n) level; vectorint ans(level); int idx level - 1, cur n; while (idx 0) { ans[idx--] cur; if (level 1) break; int loc ((1 level) - 1 - cur) 1; cur (1 (level-2)) loc; level--; } return ans; } };Python 代码class Solution: def pathInZigZagTree(self, n: int) - List[int]: def get_start(level): return 2 ** (level - 1) def get_end(level): a get_start(level) return a a - 1 level 1 while get_end(level) n: level 1 ans [0] * level idx, cur level - 1, n while idx 0: ans[idx] cur idx - 1 if level 1: break loc ((1 level) - 1 - cur) 1 cur (1 (level - 2)) loc level - 1 return ans公式验证与语言差异细节用示例 2label 26验证公式层级当前节点 curloc ((1level)-1-cur)1父节点 (1(level-2)) loc5奇数层26(31-26)1 28 2 104偶数层10(16-1-10)1 24 2 63奇数层6(8-1-6)1 02 0 22偶数层2(4-1-2)1 01 0 1得到[1,2,6,10,26]与题目输出完全一致。值得注意的源码细节在仓库原文档给出的三份代码中C 与 Python 版本在level 1时显式break避免在根节点处再执行一次无意义的公式计算此时1 (level - 2)会得到非法移位而 Java 版本依赖外层while (idx 0)的退出条件在最后一轮虽然会多算一次cur但该值不会再被使用结果不受影响。这一差异体现了「同逻辑、不同语言边界处理」的典型写法阅读源码时可对照体会。两种解法对比与选型建议维度解法一模拟解法二数学核心手段层内线性扫描定位下标再换算父节点层内对称性偏移 右移一位O(1) 定位父节点奇偶层处理分支判断偶数层反向、奇数层正向统一公式无需分支时间复杂度O(log n) 定位层级 最坏 O(n) 构造答案O(log n)空间复杂度O(1)O(1)代码量较长约 90 行三语言合计较短约 50 行三语言合计适用场景便于按题意逐步验证、思路直观面试/竞赛中追求最优复杂度与简洁实现由于label 10^6时最大层级只有 20模拟解法在实践中也完全够用但数学解法把「之字形翻转」抽象为「层内镜像偏移」更体现对满二叉树结构的本质理解是本题更推荐的最终形态。两种解法的完整代码均收录于 LeetCode/1101-1110/1104. 二叉树寻路中等.md可直接复制提交。仓库内延伸阅读与同类问题本题属于「二叉树」与「模拟」两大 Tag 的交叉题在仓库中可进一步对照Index/二叉树.md汇总了 1104 题在内的大量二叉树题解索引覆盖路径、遍历、BST 等子主题Index/模拟.md收录本题及其他按题意逐步模拟的经典题目如 Z 字形变换等LeetCode/剑指 Offer/剑指 Offer 32 - III. 从上到下打印二叉树 III中等.md同为「之字形」主题但方向相反——前者是「按之字形顺序打印整棵树的层序遍历」通过 BFS 中根据层数决定头插/尾插实现可与本题的「自底向上寻根」形成对照深化对奇偶层方向翻转的理解LeetCode/1-10/6. Z 字形变换中等.md字符串场景下的 Zigzag 规律题同样考察「按行分组的奇偶/周期规律」可作为规律建模能力的横向练习。小结二叉树寻路是一道「满二叉树结构 之字形翻转」的规律题核心在于两件事其一利用getStart / getEnd在 O(1) 内确定任意层的值区间其二理解之字形对「父 子 / 2」的破坏并用层内镜像偏移 右移定位的统一公式恢复 O(1) 寻址。掌握这套「先建模、再寻址」的思路后你不仅能 AC 本题还能迁移到其他满二叉树标号类题目如堆的父子下标换算、完全二叉树的层次定位中。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 1104 二叉树寻路用满二叉树的“定值求和”规则从之字形标签逆推回根节点LeetCode 1104 二叉树寻路用满二叉树的“定值求和”规则从之字形标签逆推回根节点 本篇技术指南基于仓库中的题解文档 1104.path in zi文档教程知识库LeetCode-Go 题解1104.Path In Zigzag Labelled Binary Tree 之字形二叉树路径推导LeetCode Go 题解1104.Path In Zigzag Labelled Binary Tree 之字形二叉树路径推导 导读 1104. Path示例工程二叉树算法体系化刷题指南LogicStack-LeetCode「二叉树」题单全解析二叉树算法体系化刷题指南LogicStack LeetCode「二叉树」题单全解析 本文以 LogicStack LeetCode 仓库中「刷穿 LeetCo教程文档上一篇FF14钓鱼计时器完整新手指南:渔人的直感3步配置、调参与排障下一篇Papermill 扩展开发实战通过 Entry Points 自定义 I/O 处理器与执行引擎创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考