[数据结构与算法]LeetCode--1104. 二叉树寻路

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)

思路：

1. 计算节点所属的层次
2. 计算节点的父节点的数值
3. 翻转父节点的数值：翻转后的父节点数值 = 父节点所在层最大值 + 最小值 - 翻转前父节点的值
4. 存放当前节点数值，将当前节点数值更新为翻转后的父节点数值，前进到父节点的层次

注意：

1. 当前节点所在层最小值与最大值：int min= (int) Math.pow(2,k - 1), max= (int) (Math.pow(2,k)-1)
2. 前一节点所在层最小值与最大值：int min= (int) Math.pow(2,k - 2), max= (int) (Math.pow(2,k - 1)-1)
3. Math.floor(Math.log(value) / Math.log(2.0)) 计算层次后需要向下取整，但是2的0次方是第一层，需要在获取对数值后再+1
4. log(0) == 1, 对于常见的对数，可以剪枝增加速度（此处不做优化）

public class Solution1104 {
	public List<Integer> pathInZigZagTree(int label) {
		// 计算 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));
	}
}