二叉树寻路——Java版

题目：

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

提示：

1 <= label <= 10^6

题解：这个题目的我的解题思路是找规律（找规律是因为和2019年河南ACM省赛的第J题有些相像），通过观察我们可以发现奇数层顺序都是正序的，偶数层的顺序都是倒序的，但是对于它们来说寻找他们的父节点找到的都是错误的（一个父节点加入为n，两个子节点为2n + 1和2n），这个时候我们需要拨正反乱，假如输入的是26（奇数层），原本的子节点应该是13，但是现在是10，但是我们现在只知道13，我们需要找出来现在占了13位置的是谁？13 - 8 + 1 = 6求出的是原来13所在的位置，8 - 6 = 2求出的倒序后对应值原来的位置，8 + 2 = 10 则是倒序后对应值原来的位置的值，则求出的是原来13位置的值变成了10。假如输入的是14（偶数层），原本的子节点是7，但是现在是4，我们将14所在层的顺序当作正序，则它的上一层就是反序，同样7 - 4 + 1 = 4求出的是7所在的位置，4 - 4 = 0求出的是求出的倒序（相对的）后对应值原来的位置，4 + 0= 4则是倒序（相对的）后对应值原来的位置的值，则求出的是原来7位置的值变成了4。我们可以总结出这样的公式：

num为父节点层的最小值，也是2的方，label是我们的输入值。
假如label为26
首先它的原父节点为label/2，label/2 - num  + 1 =  6求出的是原来13所在的位置
，num - (label/2 - num  + 1) = 2求出的倒序后对应值原来的位置，
num + (num - (label/2 - num  + 1)) = 10 则是倒序后对应值原来的位置的值，
则求出的是原来13位置的值变成了10得  3 * num - label / 2 - 1

源代码：

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        String binary = Integer.toBinaryString(label);
		int count = binary.length() - 1;
		int[] ans = new int[count + 1];
		ans[count] = label;
		for (int i = ans.length - 2; i >= 0; i--) {
			int num = 1 << (count - 1);
			ans[i] = 3 * num - label / 2 - 1;
			label = ans[i];
			count--;
		}
		List<Integer> list = new ArrayList<Integer>();
		for (int i : ans) {
			list.add(i);
		}
		return list;
    }
}

在求偶数层的时候我们也可以通过从输入值的位置找到原来所在此位置的值，再从原位置的值找到父节点，这样的话只能用if语句分别讨论了，有些麻烦。例子：比如输入值为14，14 - 8 + 1 = 7求出的是原来13所在的位置，8 - 7 = 1求出的倒序后对应值原来的位置，8 + 1 = 9 则是倒序后对应值原来的位置的值，9 / 2 = 4，则14对应的父节点为4。
如果文中我的理解有偏差或者错误，请阅读者评论指出，不胜感激。