跳转至

LeetCode: 1104. 二叉树寻路

1、题目描述

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

如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= label <= 10^6

2、解题思路

  • 实际上我们发现,后一行和起那一行还是有规律可寻,后一行的元素除以2的商,正好在前一行,只是顺序两头颠倒了,将这个关系进行翻转即可

```  1 3 2 4 5 6 7


如上面的例子, 4//2 = 2 5//2 = 2 6//2 = 3 7//2 = 3

我们将这个关系进行反转,即可得到对应的关系 上面数字的二进制形式: 100 101 110 111

用最高位的数字,然后减去非最高位的数字,再减去1 100 + 100 - 00 -1 = 111 依次类推,即可得到:

4->7 5->6 6->5 7->4 然后即可除以2得到父节点

```python
class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        tar = bin(label)[2:]

        res = [0] * len(tar)

        length = len(res)
        res[length - 1] = label
        pre = label
        for p in range(length - 2, -1, -1):
            temp = bin(pre)[2:]
            pre = (2 ** (len(temp)) - int(temp[1:], 2) - 1) // 2
            res[p] = pre

        return res