<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 {
private:
    int calculate(int label, int num, int level, vector<int>& result) {
        int end = 2*num;
        if(label >= num && label < end) {
            result.push_back(label);
            return label;
        }
        int node = calculate(label, end, level+1, result);
        bool isOddLevel = level % 2 == 1;
        int nextStart = isOddLevel ? 2*end - 1 : end;
        if(level % 2 == 1) {
            for(int i=num;i<end;i++) {
                int child1 = nextStart;
                int child2 = nextStart - 1;
                if(child1 == node || child2 == node) {
                    result.push_back(i);
                    return i;
                }
                nextStart -= 2;
            }
        }
        for(int i=end-1;i>=num;i--) {
            int child1 = nextStart;
            int child2 = nextStart + 1;
            if(child1 == node || child2 == node) {
                result.push_back(i);
                return i;
            }
            nextStart += 2;
        }
        return node;
    }
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> result;
        calculate(label, 1, 1, result);
        reverse(result.begin(), result.end());
        return result;
    }
};
7900