1104. 二叉树寻路

1
1
2
2 3
3
4 5 6 7

1
impl Solution {
2
    pub fn path_in_zig_zag_tree(label: i32) -> Vec<i32> {
3
        let layer = label.ilog2() as usize;
4

5
        let mut label = label;
6
        let mut should_reverse = false;
7
        let mut result = vec![0; layer + 1];
8

9
        for i in (0..=layer).rev() {
10
            result[i] = if should_reverse {
11
                // 2^(i+1)-1 .. x .. y .. 2^i
12
                // y - 2^i = 2^i * 2 - 1 - x
13
                // y = 2^i * 3 - 1 - x
14
                2_i32.pow(i as u32) * 3 - 1 - label
15
            } else {
16
                label
17
            };
18
            should_reverse = !should_reverse;
19
            label = label / 2;
20
        }
21

22
        result
23
    }
24
}