aboutsummaryrefslogtreecommitdiff
path: root/min_num_ops_sort_bt.c
blob: 1f4259423b18e7617f44079891d23bfd0fdd6248 (plain)
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// 2471. Minimum Number of Operations to Sort a Binary Tree by Level
#include "leetcode.h"

/*
 * you are given the 'root' of a binary tree with unique values. in one
 * operation, you can choose any two nodes at the same level and swap their
 * values. return the minimum number of operations needed to make the values at
 * each level sorted in a strictly increasing order. the level of a node is the
 * number of edges along the path between it and the root node.
 */

#define MAX_SIZE 34472

struct node_idx {
  struct TreeNode *node;
  int idx;
};

int cmp(const void *a, const void *b) {
  struct node_idx *aa = (struct node_idx *)a;
  struct node_idx *bb = (struct node_idx *)b;
  if ((*aa).node->val > (*bb).node->val)
    return 1;
  return -1;
}

int minimumOperations(struct TreeNode *root) {
  struct node_idx nodes[MAX_SIZE], new[MAX_SIZE];
  new[0].node = root;
  int len = 0, new_len = 1, tmp, ans = 0;
  struct node_idx *ptr = nodes, *new_ptr = new, *tmp_ptr;
  while (new_len) {
    tmp_ptr = new_ptr;
    new_ptr = ptr;
    ptr = tmp_ptr;
    len = new_len;
    new_len = 0;
    for (int i = 0; i < len; i++) {
      if (ptr[i].node->left) {
        new_ptr[new_len].idx = new_len;
        new_ptr[new_len++].node = ptr[i].node->left;
      }
      if (ptr[i].node->right) {
        new_ptr[new_len].idx = new_len;
        new_ptr[new_len++].node = ptr[i].node->right;
      }
    }
    qsort(ptr, len, sizeof(struct node_idx), cmp);
    for (int i = 0; i < len; i++)
      while (ptr[i].idx != i) {
        ans++;
        tmp = ptr[i].idx;
        ptr[i].idx = ptr[ptr[i].idx].idx;
        ptr[tmp].idx = tmp;
      }
  }
  return ans;
}

int main() {
  struct TreeNode *r1 = treenode_create(1);
  r1->left = treenode_create(4);
  r1->left->left = treenode_create(7);
  r1->left->right = treenode_create(6);
  r1->right = treenode_create(3);
  r1->right->left = treenode_create(8);
  r1->right->right = treenode_create(5);
  r1->right->left->left = treenode_create(9);
  r1->right->right->left = treenode_create(10);
  struct TreeNode *r2 = treenode_create(1);
  r2->left = treenode_create(3);
  r2->left->left = treenode_create(7);
  r2->left->right = treenode_create(6);
  r2->right = treenode_create(2);
  r2->right->left = treenode_create(5);
  r2->right->right = treenode_create(4);
  struct TreeNode *r3 = treenode_create(1);
  r3->left = treenode_create(2);
  r3->left->left = treenode_create(4);
  r3->left->right = treenode_create(5);
  r3->right = treenode_create(3);
  r3->right->left = treenode_create(6);
  printf("%d\n", minimumOperations(r1)); // expect: 3
  printf("%d\n", minimumOperations(r2)); // expect: 3
  printf("%d\n", minimumOperations(r3)); // expect: 0
  treenode_free(r1);
  treenode_free(r2);
  treenode_free(r3);
}