<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:
    vector<int> pathInZigZagTree(int label) {
        // row 0: 1     -> 2^0 ~ 2^1-1
        // row 1: 2~3   -> 2^1 ~ 2^2-1 (rev)
        // row 2: 4~7   -> 2^2 ~ 2^3-1
        // row 3: 8~15  -> 2^3 ~ 2^4-1 (rev)
        // row 4: 16~31 -> 2^4 ~ 2^5-1

        // 14 => row 0 => 1
        //    => row 1

        // 14 => row3: 1 (/8) => 14
        //    => row2: 0 (/4) => 4
        //    => row1: 0 (/2) => 3
        //    => row0: 0 (/1) => 1

        // 26 => row4: 10 (/16) => 26
        //    => row3: 5  (/8)  => 10
        //    => row2: 2  (/4)  => 6
        //    => row1: 1  (/2)  => 2
        //    => row0: 0  (/1)  => 1


        // (0,1) => 0
        // (2,3) => 1
        // (4,5) => 2
        // child index / 2

        // # value
        // for even row => 2^row + index
        // for odd row => 2^(row+1)-1 - index

        int max_row = 0;
        while (pow(2, max_row+1) <= label)
            max_row++;
        
        int node_index;
        if (max_row % 2 == 0)
            node_index = label - pow(2, max_row);
        else
            node_index = pow(2, max_row+1)-1 - label;

        vector<int> result;
        for (int i = max_row ; i >= 0 ; i--)
        {
            if (i % 2 == 0)
                result.push_back(pow(2, i) + node_index);
            else
                result.push_back(pow(2, i+1)-1 - node_index);

            node_index = node_index / 2;
        }
        reverse(result.begin(), result.end());

        return result;
    }
};
7800