二叉树寻路 图解题解

题目给一个标号，要哪条路径

有一棵无限大的满二叉树，也就是每层都填满节点的二叉树，标号自上而下一行行贴。第 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。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        int x = 1, i = 1;
        while ((x << 1) <= label) {
            x <<= 1;
            ++i;
        }
        vector<int> ans;
        for (; i > 0; --i) {
            ans.push_back(label);
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        int x = 1, i = 1;
        while ((x << 1) <= label) {
            x <<= 1;
            ++i;
        }
        List<Integer> ans = new ArrayList<>();
        for (; i > 0; --i) {
            ans.add(label);
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1;
        }
        Collections.reverse(ans);
        return ans;
    }
}