题目大意：
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14
输出：[1,3,4,14]
示例 2：
输入：label = 26
输出：[1,2,6,10,26]
提示：
1 <= label <= 10^6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1104
解题思路分析：
题目要求节点元素的排列顺序为蛇形排列。我们可以先将问题简化，假设二叉树所有层的节点都是按照从左向右的顺序排放，问题就会变得容易许多。试想，当一个二叉树每一层都是按照从左到右的顺序依次递增一个数字，那么这个二叉树会存在以下特征：
- 每一行的元素个数会存在2的n-1次方个。（第一层1个元素，第二层2个，第三册4个，第4层8个。。。。）
- 每一行的第一个元素一定是2的n-1次方这个数字。（第一层首元素是1，第二层是2，第3层是4，第四层是8。。。）也就是说，每一层首元素的值要等于该层元素的个数。
- 对于每个元素，它的父节点一定是当前节点值除以2。反过来说，每个元素的两个子节点分别是当前元素值乘以2和当前元素值乘以2再加1。（5的子元素分别是10和11，10和11的母元素都是5）
有了以上的特征，通过给定的数字我们可以轻松的找到其母元素（除以2），一直能找到二叉树的根（元素1）。
这时再考虑二叉树在蛇形排列的情况下如何找到母节点。虽然题目说的是奇数行正序，偶数行倒序的方式排列，但是反过来，奇数行倒序偶数行正序的方式并不会影响最终的结果。简单来说，只要保证相邻行的排序方式是相反的即可。
这样问题就转化为：当已知某一行的某个节点，如何找到该行内对应该节点的对称节点问题。我们举例来说明，比如当前行为4，当前元素为9，那么当前行的总节点数应该为8（2的4-1次方），同时该行的首元素也是8。所以元素9在正序时的index应该为1（9-8=1。注意下标从0开始，1对应的是正数第2个），肉眼可看出相对称倒序倒序坐标应该是6（倒数第二个）。也就是当前层最大index（7）减去正序index（1）的值。因此，正序第6个元素应该是首元素加上6。
最后看下完整代码：
public List<Integer> pathInZigZagTree(int label) {
int current = label;
int row = 0;
// 先求出label所在的行数。
while(current > 0){
current /= 2;
row++;
}
List<Integer> res = new ArrayList<>(); // 返回结果
current = label;
boolean isReverse=false; // 定义当前行是否需要反转
while(current >= 1){
if(isReverse){ // 如果需要反转
int count = (int)Math.pow(2, row-1); // 计算当前行元素个数
int reverseIndex = (count - 1) - (current - count); // 计算
res.add(0, count + reverseIndex); // 将对称值加到结果集中
}else{
res.add(0, current); // 如果不需要反转，直接将当前值加入到结果集
}
current /= 2; // 找到母节点
row--; // 行数减
isReverse = !isReverse; // 更新反转flag
}
return res;
}本题解法用时0ms。
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1104-path-in-zigzag-labelled-binary-tree-解题思路分析/