题目描述
在一棵无限的二叉树上，每个节点都有两个子节点，节点按照下图顺序排列，给定一个节点，求该节点到根节点的路径。
如：输入节点14，返回[1，3，4，14]
思路
这道题我认为是到数学题，本质上是要找到知道子节点退出父节点的公式和该节点位于第几层，然后不断的往上求父节点的值就可以了。
试想如果节点排序是一个方向，而不是交错的排列，如下图：
那么4=22，5=22+1，6=32，7=32+1
即：节点x，其左孩子=2x，右孩子=2x+1
上面是节点的顺序是一个方向的情况，如果按照题目的顺序又是怎么样呢？
举个例子：1 2 3 4 5 6 7 8
现在变成了8 7 6 5 4 3 2 1 ，相当于位置发生了镜像交换，
1—>8 2—>7 3—>6 4—>5
他们加起来的总数是不变得，所以知道1 可以 通过（1+8）-1计算出8
假设这一排个数为T个，那么第x个数镜像交换后的值为
（第1个数+第T个数）-第x个数
回到题目中，5 的左孩子本来是10 ，但是现在被镜像交换了，所以可以求得5现在的左孩子是：（8+15）-10 = 13
同理：7现在的左孩子是：（8+15）-14 = 9
由于这棵树每个节点都有左右孩子，第L层的第一个值是：2^L, 最后一个值是：2^(L+1) - 1
假设节点N，位于第L层，那么其左节点=2^L + 2^(L+1)-1 - 2N
那么知道一个节点反推其父节点，比如知道左节点的值left，求父节点的值：
父节点=(2^L + 2^(L+1) -1-left)/2
比如：5 = (2^3 + 2^4 -1-13)/2 = (8+15-13)/2 = 5
刚才那是左节点的情况，其实右节点推父节点也是一样的：
比如：5 = (2^3 + 2^4-1-12)/2 = (8+15-12)/2 = 11/2 = 5
因为int 除以 int 最后小数被忽略了，所以结果还是5
所以我们得到了知道子节点求父节点的公式：(2^L + 2^L +1-1-left)/2
现在唯一不知道的就是怎么求出L，即子节点是在那一层，假设节点值为N，求L：
不慌，虽然数学老师教我们的知识都差不多忘了，但是我们是程序员，有本办法，从前面知道每一层的数都在 2^L 至 2^(L+1) -1 之间，所以大不了写个循环判断嘛，很简单，另一个办法就是想起被数学支配的恐惧：直接求对数，L=logN/log2+1 别问，问就是不知道
所以到此我们总结下，已知节点N，求其父节点步骤：
- 求出N所在层，即：L = logN/log2+1
- 再求父节点：(2^L + 2^(L+1) -1-N)/2
有了两个公式代码就好写了
实现
fun pathInZigZagTree(label: Int): List<Int> {
var level = (Math.log(label.toDouble()) / Math.log(2.0)).toInt() + 1//求出节点所在的层
println(level)
val list = arrayListOf<Int>()
list.add(label)
var result: Int = label
while (level > 1) {//有多少层，就有多少个父节点
result = p(result, level--)
list.add(0, result)
}
return list
}
fun p(label: Int, level: Int): Int {
println("" + label + " " + level)
var l = level - 1//
val total: Int = (Math.pow(2.0, l.toDouble()) + Math.pow(2.0, (l + 1).toDouble()) - 1).toInt() //求出这一层首个节点值+最后个节点值总和
return (total - label) / 2//求出父节点值
}
