1104. Path In Zigzag Labelled Binary Tree**

标签: LeetCode  leetcode  算法

1104. Path In Zigzag Labelled Binary Tree**

https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/

题目描述

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

C++ 实现 1

解决这道题需要仔细找规律.

在这里插入图片描述

class Solution {
private:
    int get_row(int label) {
        int row = -1;
        while (label) {
            row += 1;
            label /= 2;
        }
        return row;
    }
public:
    vector<int> pathInZigZagTree(int label) {
        int row = get_row(label);
        vector<int> res{label};
        while (row) {
            int N = int(std::pow(2, row + 1)) - 1 + int(std::pow(2, row));
            int cur = res.back();
            int prev = (N - cur) / 2;
            res.push_back(prev);
            row --;
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
};
版权声明:本文为Eric_1993原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Eric_1993/article/details/104580062