思路： 通过当前label计算父节点
题目限制 1 <= label <= 10^6
完全二叉树每一层的节点和节点开始数字为：
1
2
4
8
16
32
...
所以每一层的数为 []int{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576}
- 提前计算每一层的数量。
- 遍历找到当前lablel所在的层。当前层最后一个节点为 last - 1。因为这个二叉树是蛇形走位。所以 上层节点所在对应层的偏移是 (last - 1 - label)/2
- 计算上一层的起始位置为last/4。
- 上一层label即为 (last - 1 - label)/2 + last/4。
- 递归知道label = 1
var start = []int{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576}
func pathInZigZagTree(label int) []int {
if label == 1 {
return []int{1}
}
last := 0
for i := 0; i < len(start); i++ {
if label < start[i] {
last = start[i]
break
}
}
idx := (last - label - 1) / 2
return append(pathInZigZagTree(last/4+idx), label)
}
