題目描述
在一棵無限的二叉樹上，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，節(jié)點(diǎn)按照下圖順序排列，給定一個(gè)節(jié)點(diǎn)，求該節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。
如：輸入節(jié)點(diǎn)14，返回[1，3，4，14]
思路
這道題我認(rèn)為是到數(shù)學(xué)題，本質(zhì)上是要找到知道子節(jié)點(diǎn)退出父節(jié)點(diǎn)的公式和該節(jié)點(diǎn)位于第幾層，然后不斷的往上求父節(jié)點(diǎn)的值就可以了。
試想如果節(jié)點(diǎn)排序是一個(gè)方向，而不是交錯(cuò)的排列，如下圖：
那么4=22，5=22+1，6=32，7=32+1
即：節(jié)點(diǎn)x，其左孩子=2x，右孩子=2x+1
上面是節(jié)點(diǎn)的順序是一個(gè)方向的情況，如果按照題目的順序又是怎么樣呢？
舉個(gè)例子：1 2 3 4 5 6 7 8
現(xiàn)在變成了8 7 6 5 4 3 2 1 ，相當(dāng)于位置發(fā)生了鏡像交換，
1—>8 2—>7 3—>6 4—>5
他們加起來的總數(shù)是不變得，所以知道1 可以 通過（1+8）-1計(jì)算出8
假設(shè)這一排個(gè)數(shù)為T個(gè)，那么第x個(gè)數(shù)鏡像交換后的值為
（第1個(gè)數(shù)+第T個(gè)數(shù)）-第x個(gè)數(shù)
回到題目中，5 的左孩子本來是10 ，但是現(xiàn)在被鏡像交換了，所以可以求得5現(xiàn)在的左孩子是：（8+15）-10 = 13
同理：7現(xiàn)在的左孩子是：（8+15）-14 = 9
由于這棵樹每個(gè)節(jié)點(diǎn)都有左右孩子，第L層的第一個(gè)值是：2^L, 最后一個(gè)值是：2^(L+1) - 1
假設(shè)節(jié)點(diǎn)N，位于第L層，那么其左節(jié)點(diǎn)=2^L + 2^(L+1)-1 - 2N
那么知道一個(gè)節(jié)點(diǎn)反推其父節(jié)點(diǎn)，比如知道左節(jié)點(diǎn)的值left，求父節(jié)點(diǎn)的值：
父節(jié)點(diǎn)=(2^L + 2^(L+1) -1-left)/2
比如：5 = (2^3 + 2^4 -1-13)/2 = (8+15-13)/2 = 5
剛才那是左節(jié)點(diǎn)的情況，其實(shí)右節(jié)點(diǎn)推父節(jié)點(diǎn)也是一樣的：
比如：5 = (2^3 + 2^4-1-12)/2 = (8+15-12)/2 = 11/2 = 5
因?yàn)閕nt 除以 int 最后小數(shù)被忽略了，所以結(jié)果還是5
所以我們得到了知道子節(jié)點(diǎn)求父節(jié)點(diǎn)的公式：(2^L + 2^L +1-1-left)/2
現(xiàn)在唯一不知道的就是怎么求出L，即子節(jié)點(diǎn)是在那一層，假設(shè)節(jié)點(diǎn)值為N，求L：
不慌，雖然數(shù)學(xué)老師教我們的知識(shí)都差不多忘了，但是我們是程序員，有本辦法，從前面知道每一層的數(shù)都在 2^L 至 2^(L+1) -1 之間，所以大不了寫個(gè)循環(huán)判斷嘛，很簡(jiǎn)單，另一個(gè)辦法就是想起被數(shù)學(xué)支配的恐懼：直接求對(duì)數(shù)，L=logN/log2+1 別問，問就是不知道
所以到此我們總結(jié)下，已知節(jié)點(diǎn)N，求其父節(jié)點(diǎn)步驟：
- 求出N所在層，即：L = logN/log2+1
- 再求父節(jié)點(diǎn)：(2^L + 2^(L+1) -1-N)/2
有了兩個(gè)公式代碼就好寫了
實(shí)現(xiàn)
fun pathInZigZagTree(label: Int): List<Int> {
var level = (Math.log(label.toDouble()) / Math.log(2.0)).toInt() + 1//求出節(jié)點(diǎn)所在的層
println(level)
val list = arrayListOf<Int>()
list.add(label)
var result: Int = label
while (level > 1) {//有多少層，就有多少個(gè)父節(jié)點(diǎn)
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() //求出這一層首個(gè)節(jié)點(diǎn)值+最后個(gè)節(jié)點(diǎn)值總和
return (total - label) / 2//求出父節(jié)點(diǎn)值
}
