二叉树寻路 图解题解

这道题到底在问什么

输入

label = 14

输出

[1,3,4,14]

输入

label = 26

输出

[1,2,6,10,26]

最优解：一步一步想明白

1. 3记牢两步:先翻倍定行,再「镜像加折半」逐行爬到父节点。镜像 = 本行最小加最大减自己,目的就是抵消之字形的方向翻转。下面每一帧都在套这套规则。
2. 4行1:1 行2:3 2 行3:4 5 6 7 行4:15 14 ...先看清这棵树长什么样。树是无限大的,这里只画出和我们这次寻路有关的一小块。每个圆圈里的数字就是这个节点的标号,注意行与行之间,编号方向是反复掉头的。
3. 5行1 范围 [1,1]最上面第 1 行,只有一个根节点,标号就是 1。它的范围是 2 的 0 次方 到 2 的 1 次方减 1,也就是只有 1 这一个数。第 1 行算奇数行,从左到右编。
4. 6行2 范围 [2,3] · 从右往左第 2 行有两个节点,标号占 2 和 3。可它是偶数行,要从右往左编号,于是右边那个反而是 2、左边那个是 3。看清楚了吗,这一行被掉了个头,这正是之字形最容易绕晕的地方。
5. 7行3 范围 [4,7] · 从左往右第 3 行是奇数行,又回到从左往右,标号规规矩矩是 4、5、6、7。可以看到方向又掉回来了,和第 2 行正好相反。
6. 8行4 范围 [8,15] · 从右往左第 4 行又是偶数行,再次从右往左,整行应该是 15、14、13 一直到 8。屏幕地方有限,只画出靠左的 15 和 14 两个,它们正是节点 4 的两个孩子。我们要找的 14 就藏在这一行里。
7. 9x = 1,行 i = 1开始定位 14 在第几行。从 x 等于 1、i 等于 1 出发,x 始终代表第 i 行标号范围的起点、也就是这一行的最小标号 2 的 (i-1) 次方(注意之字形里偶数行被翻转,屏幕上最左端那个未必是它)。试着翻倍:1 乘 2 等于 2,2 还小于等于 14,说明 14 在更下面,往下走一行。
8. 10x = 2,行 i = 2x 翻成 2,i 变成 2,现在停在第 2 行。再翻倍:2 乘 2 等于 4,4 仍然小于等于 14,14 还在更深处,接着往下。
9. 11x = 4,行 i = 3x 翻成 4,i 变成 3。再翻倍:4 乘 2 等于 8,8 还是小于等于 14,14 依旧在下面,再下一行看看。
10. 12x = 8,行 i = 4 · x*2 = 16 > 14 停x 翻成 8,i 变成 4。这回再翻倍是 16,16 已经大于 14 了,不能再往下,停手。于是确定 14 就落在第 4 行,这一行标号范围是 8 到 15。
11. 13行号 i = 4,答案将有 4 个标号行号定下来了,14 在第 4 行。因为它在第 4 行,从根到它一共要经过 4 个节点,所以答案会是 4 个标号。接下来从 14 出发,一行一行往上爬到根。
12. 14label = 14,本行范围 [8,15]现在处理标号 14,它在第 4 行,这一行的标号范围是 8 到 15。普通满二叉树里父节点就是自己除以 2,但偶数行被翻转过,直接除不是可靠通用规则,这里统一先镜像再折半。
13. 15镜像 = 8 + 15 - 14 = 9做镜像:把本行的最小 8 加最大 15,再减掉自己 14,得到 9。这个 9 就是 14 在本行里左右对称的那个位置。镜像这一下,正好抵消了相邻两行方向相反带来的错位。
14. 16父 = 9 / 2 = 4把镜像值 9 除以 2,向下取整得到 4。神奇的地方在这里:因为上一行的编号方向和这一行正好相反,镜像加折半两步一合,4 不是别的中间量,它就是 14 父节点的真实标号。把 4 记下来,继续往上爬。
15. 17label = 4,本行范围 [4,7]现在处理标号 4,它在第 3 行,这一行的标号范围是 4 到 7。普通满二叉树里父节点就是自己除以 2,但偶数行被翻转过,直接除不是可靠通用规则,这里统一先镜像再折半。
16. 18镜像 = 4 + 7 - 4 = 7做镜像:把本行的最小 4 加最大 7,再减掉自己 4,得到 7。这个 7 就是 4 在本行里左右对称的那个位置。镜像这一下,正好抵消了相邻两行方向相反带来的错位。
17. 19父 = 7 / 2 = 3把镜像值 7 除以 2,向下取整得到 3。神奇的地方在这里:因为上一行的编号方向和这一行正好相反,镜像加折半两步一合,3 不是别的中间量,它就是 4 父节点的真实标号。把 3 记下来,继续往上爬。
18. 20label = 3,本行范围 [2,3]现在处理标号 3,它在第 2 行,这一行的标号范围是 2 到 3。普通满二叉树里父节点就是自己除以 2,但偶数行被翻转过,直接除不是可靠通用规则,这里统一先镜像再折半。
19. 21镜像 = 2 + 3 - 3 = 2做镜像:把本行的最小 2 加最大 3,再减掉自己 3,得到 2。这个 2 就是 3 在本行里左右对称的那个位置。镜像这一下,正好抵消了相邻两行方向相反带来的错位。
20. 22父 = 2 / 2 = 1把镜像值 2 除以 2,向下取整得到 1。神奇的地方在这里:因为上一行的编号方向和这一行正好相反,镜像加折半两步一合,1 不是别的中间量,它就是 3 父节点的真实标号。把 1 记下来,继续往上爬。
21. 23label = 1 已是根,停止爬到第 1 行了,当前标号是 1,也就是根。根没有父节点,上爬到此结束。一路自底向上收集到的标号是 14、4、3、1,马上把它倒过来就是答案。
22. 24自底向上 14, 4, 3, 1 ➜ 倒序 1, 3, 4, 14上爬是从底往上收的,顺序是 14、4、3、1。题目要的是从根到 14 自上而下的顺序,所以把它倒过来,得到 1、3、4、14。
23. 25答案 [1,3,4,14]紫色这条链就是从根到 14 的路:1 到 3 到 4 到 14,答案 [1,3,4,14]。回顾一下,我们压根没有真的把这棵无限树建出来,只靠翻倍定行、再镜像折半逐行上爬,几步就把路径算了出来。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问