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
.
Example 1:
Input: label = 14 Output: [1,3,4,14]
Example 2:
Input: label = 26 Output: [1,2,6,10,26]
Constraints:
1 <= label <= 10^6
Solution: Math
Time complexity: O(logn)
Space complexity: O(logn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: vector<int> pathInZigZagTree(int label) { deque<int> ans; while (label) { ans.push_front(label); int h = 31 - __builtin_clz(label); label = ((1 << h) + (1 << (h + 1)) - 1 - label) / 2; } return {begin(ans), end(ans)}; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment