跳转至

1104. 二叉树寻路

题目描述

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

 

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

 

提示：

  • 1 <= label <= 10^6

解法

方法一：数学

思考

普通完全二叉树中父结点为 \(\lfloor \textit{label}/2\rfloor\)，但本题奇数行与偶数行标记方向相反，该公式不再成立。第 \(i\) 层编号区间为 \([2^{i-1},2^i-1]\)，反向层上结点关于区间中心对称，互补编号为 \(2^{i-1}+2^i-1-\textit{label}\)，真实父结点即该互补编号除以 \(2\)。

先求出 \(\textit{label}\) 所在层数，再自底向上反复取互补并右移，把路径写入对应下标，自然得到从根到该结点的序列。

对于一棵完全二叉树，第 \(i\) 行的节点个数为 \(2^{i-1}\)，第 \(i\) 行的节点编号范围为 \([2^{i-1}, 2^i - 1]\)。而题目中对于奇数行，按从左到右的顺序进行标记，对于偶数行，按从右到左的顺序进行标记。所以对于第 \(i\) 行的节点 \(label\)，它的互补节点编号为 \(2^{i-1} + 2^i - 1 - label\)。所以节点 \(label\) 的实际父节点编号为 \((2^{i-1} + 2^i - 1 - label) / 2\)。我们可以通过不断地求互补节点编号和父节点编号，直到到达根节点，即可得到从根节点到节点 \(label\) 的路径。

最后，我们需要将路径反转，因为题目要求路径是从根节点到节点 \(label\) 的路径。

时间复杂度 \(O(\log n)\)，其中 \(n\) 为节点 \(label\) 的编号。忽略答案的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func pathInZigZagTree(label int) (ans []int) {
    x, i := 1, 1
    for x<<1 <= label {
        x <<= 1
        i++
    }
    for ; i > 0; i-- {
        ans = append(ans, label)
        label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
    }
    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
        ans[i], ans[j] = ans[j], ans[i]
    }
    return
}

评论