Skip to content

2471. Minimum Number of Operations to Sort a Binary Tree by Level 👍

  • 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
29
30
31
32
class Solution {
 public:
  int minimumOperations(TreeNode* root) {
    int ans = 0;
    queue<TreeNode*> q{{root}};

    // e.g. vals = [7, 6, 8, 5]
    // [2, 1, 3, 0]: Initialize the ids based on the order of vals.
    // [3, 1, 2, 0]: Swap 2 with 3, so 2 is in the right place (i == ids[i]).
    // [0, 1, 2, 3]: Swap 3 with 0, so 3 is in the right place.
    while (!q.empty()) {
      vector<int> vals;
      vector<int> ids(q.size());
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode* node = q.front();
        q.pop();
        vals.push_back(node->val);
        if (node->left != nullptr)
          q.push(node->left);
        if (node->right != nullptr)
          q.push(node->right);
      }
      iota(ids.begin(), ids.end(), 0);
      ranges::sort(ids, [&vals](int i, int j) { return vals[i] < vals[j]; });
      for (int i = 0; i < ids.size(); ++i)
        for (; ids[i] != i; ++ans)
          swap(ids[i], ids[ids[i]]);
    }

    return ans;
  }
};

 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
class Solution {
  public int minimumOperations(TreeNode root) {
    int ans = 0;
    Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));

    // e.g. vals = [7, 6, 8, 5]
    // [2, 1, 3, 0]: Initialize the ids based on the order of vals.
    // [3, 1, 2, 0]: Swap 2 with 3, so 2 is in the right place (i == ids[i]).
    // [0, 1, 2, 3]: Swap 3 with 0, so 3 is in the right place.
    while (!q.isEmpty()) {
      List<Integer> vals = new ArrayList<>();
      List<Integer> ids = new ArrayList<>();
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode node = q.poll();
        vals.add(node.val);
        if (node.left != null)
          q.offer(node.left);
        if (node.right != null)
          q.offer(node.right);
      }
      for (int i = 0; i < vals.size(); ++i)
        ids.add(i);
      Collections.sort(ids, (i, j) -> vals.get(i) - vals.get(j));
      for (int i = 0; i < ids.size(); ++i)
        for (; ids.get(i) != i; ++ans)
          swap(ids, i, ids.get(i));
    }

    return ans;
  }

  private void swap(List<Integer> ids, int i, int j) {
    final int temp = ids.get(i);
    ids.set(i, ids.get(j));
    ids.set(j, temp);
  }
}

 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:
  def minimumOperations(self, root: TreeNode | None) -> int:
    ans = 0
    q = collections.deque([root])

    # e.g. vals = [7, 6, 8, 5]
    # [2, 1, 3, 0]: Initialize the ids based on the order of vals.
    # [3, 1, 2, 0]: Swap 2 with 3, so 2 is in the right place (i == ids[i]).
    # [0, 1, 2, 3]: Swap 3 with 0, so 3 is in the right place.
    while q:
      vals = []
      for _ in range(len(q)):
        node = q.popleft()
        vals.append(node.val)
        if node.left:
          q.append(node.left)
        if node.right:
          q.append(node.right)
      # O(n^2logn), which is not great and leads to TLE.
      ids = [sorted(vals).index(val) for val in vals]
      for i in range(len(ids)):
        while ids[i] != i:
          j = ids[i]
          ids[i] = ids[j]
          ids[j] = j
          ans += 1

    return ans