1104. Path In Zigzag Labelled Binary Tree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        // [1]
        // [2, 3]
        // [4, 5, 6, 7]
        // [8, 9, 10, 11, 12, 13, 14, 15]

        int start = 1, end = 1;
        int level = 1;
        while (label < start || label > end) {
            int size = end - start + 1;
            int doubleSize = 2 * size;

            start = end + 1;
            end = end + doubleSize;
            level++;
        }

        // now: label between start and end
        LinkedList<Integer> path = new LinkedList<>();
        while (level > 0) {
            path.addFirst(label);

            if ((level & 1) == 0) {
                // 偶数行
                label = (start + (end - label)) / 2;
            } else {
                int prevStart = start / 2, prevEnd = end / 2;
                label = prevStart + (prevEnd - label / 2);
            }

            start /= 2;
            end /= 2;
            level--;
        }

        return path;
    }
}

References

1104. Path In Zigzag Labelled Binary Tree