<p>In an infinite binary tree where every node has two children, the nodes are labelled in row order.</p>

<p>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.</p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/06/24/tree.png" style="width: 300px; height: 138px;" /></p>

<p>Given the <code>label</code> of a node in this tree, return the labels in the path from the root of the tree to the&nbsp;node with that <code>label</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> label = 14
<strong>Output:</strong> [1,3,4,14]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> label = 26
<strong>Output:</strong> [1,2,6,10,26]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= label &lt;= 10^6</code></li>
</ul>

class Solution {
public:
    /*
        14% = 0
        14% = 2
        14%4 = 
    */
    // vector<int> pathInZigZagTree(int n) {
    //     vector<int> res;
    //     for(; n; n/=2) res.push_back(n); // build orginal path first
    //     for(int i=res.size()-1; i>=0; --i) // invert parent label
    //         if(i%2) res[i] = (1 << (res.size() - i - 1)) * 3 - res[i] - 1;
    //     return {res.rbegin(), res.rend()};
    // }   
    
    // The maximum label in the level is 1 << level - 1, and minimum is 1 << (level - 1). We will use this fact to "invert" the parent label.
    vector<int> pathInZigZagTree(int n) {
        // // int l = 0;
        // // while (1 << l <= n) ++l;
        // int l = log2(n)+1;
        // vector<int> res(l);
        // for(; n >= 1; n /= 2, --l) {
        //     res[l - 1] = n;
        //     n = (1 << l) - 1 - n + (1 << (l - 1));
        // }
        // return res;

        // 26
        // 32-1-26+16 = 21
        // 32-1 - (26-16) = 21
        // curLevel = 1<<(l+1), preLevel = 1<<l;
        // invert parent label curLevel-1-(n-preLevel)
        // =>
        // curLevel: m
        // n-preLevel: i
        // m-i-1
        
        // int l = log2(n); // level
        // int l = 64 - __builtin_clzl(n) - 1; // count leading zeroes for long 
        int l = 32 - __builtin_clz(n)-1;  // count leading zeroes
        vector<int> res(l+1);
        for(; n >= 1; n /= 2, --l) {
            res[l] = n;
            // n = (1 << (l+1)) - 1 - n + (1 << l); // invert parent label
            n = (1 << (l+1)) - 1 - (n - (1 << l)); // invert parent label
        }
        return res;
    }
    
    
    // vector<int> pathInZigZagTree(int n) {
    //     vector<int> res;
    //     for(int l = log2(n); n>1; n/=2, --l) {
    //         cout << l << endl;
    //         res.push_back(l%2 ? n : (int)pow(l, 2)-(n%(int)pow(l-1,2)));
    //     }
    //     res.push_back(1);
    //     return {res.rbegin(), res.rend()};
    // }
};
7400