1104. 二叉树寻路

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
40
41
class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> pathInZigZagTree(int label) {
        // 层数
        int n = 1;
        int x = label;
        while (x / 2 != 0) {
            x = x / 2;
            n++;
        }

        int tmp = label;
        while (n > 0) {
            ans.add(tmp);
            int max = (int)Math.pow(2, n) - 1;
            int min = (int)Math.pow(2, n - 1);
            if (n % 2 == 0) {
                // 偶数层,反向
                while (max != tmp) {
                    max--;
                    min++;
                }

                // 当max==tmp时,min为角标
                tmp = min / 2;
            }else {
                // 奇数层,正向
                while (min != tmp) {
                    max--;
                    min++;
                }
                // min==tmp时,max为数字
                tmp = max / 2;
            }
            n--;
        }
        Collections.sort(ans);
        return ans;
    }
}