Skip to content

1104. Path In Zigzag Labelled Binary Tree 👍

  • Time:
  • Space: 
 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
class Solution {
 public:
  vector<int> pathInZigZagTree(int label) {
    deque<int> ans;
    int level;

    for (int l = 0; l < 21; ++l)
      if (pow(2, l) > label) {
        level = l - 1;
        break;
      }

    if (level % 2 == 1)
      label = boundarySum(level) - label;

    for (int l = level; l >= 0; --l) {
      ans.push_front(l % 2 == 0 ? label : boundarySum(l) - label);
      label /= 2;
    }

    return {ans.begin(), ans.end()};
  }

 private:
  int boundarySum(int level) {
    return pow(2, level) + pow(2, level + 1) - 1;
  }
};

 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
class Solution {
  public List<Integer> pathInZigZagTree(int label) {
    LinkedList<Integer> ans = new LinkedList<>();
    int level = 0;

    for (int l = 0; l < 21; ++l)
      if (Math.pow(2, l) > label) {
        level = l - 1;
        break;
      }

    if (level % 2 == 1)
      label = boundarySum(level) - label;

    for (int l = level; l >= 0; --l) {
      ans.addFirst(l % 2 == 0 ? label : boundarySum(l) - label);
      label /= 2;
    }

    return new ArrayList<>(ans);
  }

  private int boundarySum(int level) {
    return (int) Math.pow(2, level) + (int) Math.pow(2, level + 1) - 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def pathInZigZagTree(self, label: int) -> list[int]:
    def boundarySum(level: int):
      return 2**level + 2**(level + 1) - 1

    ans = []

    for l in range(21):
      if 2**l > label:
        level = l - 1
        break

    if level % 2 == 1:
      label = boundarySum(level) - label

    for l in reversed(range(level + 1)):
      ans.append(label if l % 2 == 0 else boundarySum(l) - label)
      label //= 2

    return ans[::-1]