题目描述
原题链接
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14
输出：[1,3,4,14]
示例 2：
输入：label = 26
输出：[1,2,6,10,26]
提示：
1 <= label <= 10^6
题目分析
本题和二叉树的关系不大，二叉树展示了数据的排列结构。比较容易想到的方法是找规律然后逐次推出父节点的方法。
以下图为例，
例如当label=12时，由于
8
≤
12
≤
15
8\leq12\leq15
8≤12≤15，所以确定11在第4行，11和本行最小的数8相差4，两个子节点对应一个父节点，因此可以知道12和8的父节点差了
f
l
o
o
r
(
(
12
?
8
)
/
2
)
=
2
floor((12-8)/2)=2
floor((12?8)/2)=2，8的父节点就是
8
?
1
=
7
8-1=7
8?1=7，因此12对应的父节点就是
7
?
2
=
5
7-2=5
7?2=5，以此类推，得到余下的父节点。
class Solution {
public:
vector<int> pathInZigZagTree(int label) {
int row = 0;
//先确定label在哪一行
while(label >= pow(2, ++row)){}
vector<int> ans(row--, label);
while(row > 0){
//找出label的父节点和本行最小的数的父节点的差值
int seq = (label - pow(2, row)) / 2;
//用label的父节点更新label
label = pow(2, row) - 1 - seq;
ans[--row] = label;
}
return ans;
}
};