Leetcode 1104: Path In Zigzag Labelled Binary Tree

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

Notes:

This question is mainly for deriving a formula from observation, so it is not on the capability for coding...

Here are some of the key facts:

1): each layer has 2^n elements, where n is the layer number starting with 0;

2): if we have a label with value as val, then its layer is log2(val);

3): for each layer, the label range from [2^n, 2^(n+1) - 1];

The key is to find the parent element given the val.

4): at the same layer, the number of smaller elements are: rd = val - 2^n;

5): on the parent layer (if it has parent layer), there are (rd/2) more smaller elements smaller than its parent element.

Thus its parent value is:  val - rd - rd/2 - 1.

After having this information, we solve this question with recursion: the base case is that when the val == 0, we should stop.

See the code below:

class Solution {
public:
	vector<int> pathInZigZagTree(int label) {
        vector<int> res;
        dfs(res, label);
        reverse(res.begin(), res.end());
        return res;
    }
private:
    void dfs(vector<int> &r, int v) {
        if(v==0) return;
        r.push_back(v);
        int n = floor(log2(v)), rd = v - pow(2, n);
        dfs(r, v-rd-rd/2-1);
    }
};