每日算法题—二叉树寻路

题目描述

在一棵无限的二叉树上，每个节点都有两个子节点，节点按照下图顺序排列，给定一个节点，求该节点到根节点的路径。

如：输入节点14，返回[1，3，4，14]

思路

这道题我认为是到数学题，本质上是要找到知道子节点退出父节点的公式和该节点位于第几层，然后不断的往上求父节点的值就可以了。
试想如果节点排序是一个方向，而不是交错的排列，如下图：

回到题目中，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，求其父节点步骤：

1. 求出N所在层，即：L = logN/log2+1
2. 再求父节点：(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//求出父节点值
    }