LeetCode 1104. 二叉树寻路

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数学 树 二叉树

题目描述

✅ 1104. 二叉树寻路

image-20260929074803086

image-20260929074803153

题意分析

一棵无限满二叉树按层连续编号，但相邻层的编号方向相反：根所在第一行从左向右，第二行从右向左，之后交替。给定一个节点标签 label，返回从根到它经过的全部标签，包含根和目标本身。

每层使用的数值范围与普通层序编号相同，只是左右方向可能反转。因此题目不是在普通二叉树中按标签直接除二，也不需要构造或遍历整棵无限树；每个节点的父亲唯一，可以从目标反向求路径。

解法：从节点回溯到根

核心思路

[!blue]

代码把根记为第零层。第 level 层的标签范围是 start = 2^level 到 end = 2^(level + 1) - 1，不论该层朝哪边编号，这两个端点都不变。同层某个标签反转方向后的对应值为 start + end - label，因为左右对称位置的标签和固定。

普通从左到右编号时，孩子编号除以二并向下取整，就是父编号。若当前层是倒序、父层是正序，先把当前标签镜像回普通方向，再除二，得到父标签 floor((start + end - label) / 2)。

若当前层是正序、父层是倒序，先求普通父编号 floor(label / 2)，再在父层的范围 [start / 2, start - 1] 内镜像。父标签为 start / 2 + start - 1 - floor(label / 2)，化简后仍等于上面的统一公式。因此无需每层单独维护方向标记，只要更新本层端点就能求父标签。

先根据标签大小找到当前层，从目标开始循环：记录当前标签，套用公式转到父节点，层号减一。每轮严格向上一层，最终记录根标签一；根再转移为零后结束，不会真的继续处理负层号。

这样得到的是目标到根的逆向路径，最后反转列表即可。所有计算只涉及路径上的节点，开销由树高而不是标签范围中的全部节点决定。

解题步骤

  1. 从零层开始递增层号，找到包含 label 的二进制层级范围。
  2. 将当前标签加入路径，计算本层 start、end。
  3. 令 label = (start + end - label) / 2，层号减一，继续向上。
  4. 标签变为零后结束，反转已记录路径并返回。

代码实现

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 + 1))$，定位层数、向上回溯和反转都只处理与层数同阶的工作，label 指原始目标标签。
  • 空间复杂度：返回路径占 $O(\log(label + 1))$，除此之外只保存当前标签、层号与端点，辅助空间为 $O(1)$。

关键点总结

[!green]

  • 方向交替不改变每层数值范围，层内镜像由端点和减去当前标签得到。
  • 当前层倒序与父层倒序两种情况，都能归结为同一个父标签公式。
  • 从目标求唯一父节点更直接，反转后才得到根到目标的要求顺序。

易错点总结

[!yellow]

  • 直接用标签除二，忽略了之字形标签与普通位置编号的区别。
  • 只在当前层倒序时修正，遗漏当前层正序但父层倒序的情况。
  • 将代码的零基层号与题目的一基行号混用，会得到错误的幂次范围。
  • 在标签为一之前就停止，导致路径中缺少根节点。
  • 忘记反转，返回的是目标到根，而非根到目标。

相似题目

题目 难度 关联与区别
662. 二叉树最大宽度 中等 普通位置编号满足父子倍数关系，本题锯齿标签需先做层内镜像，不能直接除2。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/67484804
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！