1104. 二叉树寻路
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14 输出：[1,3,4,14]
示例 2：
输入：label = 26 输出：[1,2,6,10,26]
提示：
1 <= label <= 10^6原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-15 11:16:40
class Solution:
def pathInZigZagTree(self, label: int) -> List[int]:
# 先把不是Z字型的父节点算出来，顺序完全二叉树的父节点是 node//2
# 基于一个归纳，当前节点除以2取整就是父节点的值
res = []
while label != 1:
res.append(label)
label//=2
res.append(1)
res.reverse()
# 从倒数第二个开始，每隔一个，找出取反相对应的值
for i in range(len(res)-2, -1, -2):
original = res[i]
#
start = 2**i
end = 2**(i+1) -1
new = start + end - original
res[i] = new
return res
python3 解法, 执行用时: 552 ms, 内存消耗: 60.5 MB, 提交时间: 2022-11-15 11:16:07
class Solution:
def pathInZigZagTree(self, label: int) -> List[int]:
g, res, sz, dp = [[1]], [], 1, 1
while sz < label:
temp = 1 << dp
tlist = [i + 1 for i in range(sz, sz + temp)]
if dp & 1:
g.append(list(reversed(tlist)))
else:
g.append(tlist)
sz += temp
dp += 1
for i in range(len(g[-1])):
if g[-1][i] == label:
res.append(label)
while dp != 1:
res.append(g[dp - 2][i // 2])
dp -= 1
i //= 2
break
return list(reversed(res))
javascript 解法, 执行用时: 60 ms, 内存消耗: 41 MB, 提交时间: 2022-11-15 11:14:20
/**
* @param {number} label
* @return {number[]}
*/
var pathInZigZagTree = function (label) {
// 目标元素位于完全二叉树的第几行
const hang = Math.ceil(Math.log2(label + 1))
// 存储结果，先将目标节点放入
const res = [label]
// 进行判断，如果目标节点本身就在偶数行，需要将其变为翻转前的节点序号，
// 以便按照一般完全二叉树找到父节点
if (hang % 2 === 0) label = Math.pow(2, hang - 1) + Math.pow(2, hang) - 1 - label
// 从目标节点向上遍历父节点，记录路径
// 目标节点已经存入，所以从上一行开始
for (let i = hang - 1; i > 0; i--) {
// 获取一般完全二叉树当前节点的父节点
label = Math.floor(label / 2)
// 如果当前行为偶数行，将其翻转后的对应位置记录
// [注意]只是向翻转后的位置记录，不需要将节点变为翻转后的节点，因为我们是按照正常节点进行遍历
if (i % 2 === 0) res.unshift(Math.pow(2, i - 1) + Math.pow(2, i) - 1 - label)
else res.unshift(label) // 如果为奇数行，直接存入父节点
}
return res // 返回结果
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-15 11:13:34
func getReverse(label, row int) int {
return 1<<(row-1) + 1<<row - 1 - label
}
func pathInZigZagTree(label int) (path []int) {
row, rowStart := 1, 1
for rowStart*2 <= label {
row++
rowStart *= 2
}
if row%2 == 0 {
label = getReverse(label, row)
}
for row > 0 {
if row%2 == 0 {
path = append(path, getReverse(label, row))
} else {
path = append(path, label)
}
row--
label >>= 1
}
for i, n := 0, len(path); i < n/2; i++ {
path[i], path[n-1-i] = path[n-1-i], path[i]
}
return
}