1104. Path In Zigzag Labelled Binary Tree - medium
문제
In an infinite binary tree where every node has two children, the nodes are labelled in row order.
In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.
Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.
제한사항
- 1 <= label <= 10^6
입출력 예
1
2
3
Example 1:
Input: label = 14
Output: [1,3,4,14]
1
2
3
Example 2:
Input: label = 26
Output: [1,2,6,10,26]
풀이
- Tree, Math
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<int> pathInZigZagTree(int label) {
if(label == 1)
return {1};
// Tree의 깊이탐색
auto findLevel = label;
int level = 0;
while(findLevel){
findLevel >>= 1;
++level;
}
// 가장 마지막원소의 값은 label이며,
// 마지막의 앞 원소의 값은
// label이 속한 트리의 깊이가 뒤집혀있든 뒤집혀있지 않든, 모두 같은 방향으로 만들어 줌
// ((2의 현재 level의 제곱) - label + (2의 현재 level-1 의 제곱) - 1) / 2
vector<int> ans(2);
ans[0] = label;
ans[1] = (pow(2, level) - label + pow(2, level - 1) - 1) / 2;
// 현재 노드의 할아버지 노드는, 손자 노드의 / 4 임
// 즉, ans[i] = ans[i - 2] / 4
--level;
int index = 0;
while(--level){
label /= 4;
ans.push_back(ans[index] / 4);
++index;
}
// Tree의 leaf노드부터 구하기 시작했으므로 역전시켜야 함
std::reverse(ans.begin(), ans.end());
return ans;
}
};