1104. 二叉树寻路
前置知识点:
二叉树的性质 性质1:二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。 性质2:深度为k的二叉树至多有2{k}-1个结点(k≥1)。 性质3:包含n个结点的二叉树的高度至少为log2 (n+1)。 性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。
数组存放二叉树的性质: 设某个节点索引值为index,则节点的 左子节点索引为:2index+1 右子节点索引为:2index+2 父节点索引为:(index-1)/2
Java中只存在计算自然对数的函数,如何计算log2? 换底公式:logx(y) =loge(y) / loge(x)
思路:
- 计算节点所属的层次
- 计算节点的父节点的数值
- 翻转父节点的数值:翻转后的父节点数值 = 父节点所在层最大值 + 最小值 - 翻转前父节点的值
- 存放当前节点数值,将当前节点数值更新为翻转后的父节点数值,前进到父节点的层次
注意:
- 当前节点所在层最小值与最大值:int min= (int) Math.pow(2,k - 1), max= (int) (Math.pow(2,k)-1)
- 前一节点所在层最小值与最大值:int min= (int) Math.pow(2,k - 2), max= (int) (Math.pow(2,k - 1)-1)
- Math.floor(Math.log(value) / Math.log(2.0)) 计算层次后需要向下取整,但是2的0次方是第一层,需要在获取对数值后再+1
- log(0) == 1, 对于常见的对数,可以剪枝增加速度(此处不做优化)
public class Solution1104 {
public List<Integer> pathInZigZagTree(int label) {
int k = logBase2FloorNum(label) + 1;
List<Integer> res = Arrays.asList(new Integer[k]);
int tempNum = label;
for (; k > 1; k--) {
res.set(k - 1, tempNum);
int min= (int) Math.pow(2,k - 2), max= (int) (Math.pow(2,k - 1)-1);
tempNum = max + min - (tempNum >> 1);
}
res.set(0, 1);
return res;
}
public int logBase2FloorNum(int value) {
if (value == 1) {
return 0;
}
return (int) Math.floor(Math.log(value) / Math.log(2.0));
}
public static void main(String[] args) {
Solution1104 solution1104 = new Solution1104();
System.out.println(solution1104.pathInZigZagTree(1));
System.out.println(solution1104.pathInZigZagTree(14));
System.out.println(solution1104.pathInZigZagTree(16));
}
}
|