aboutsummaryrefslogtreecommitdiff
path: root/min_num_ops_sort_bt.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_num_ops_sort_bt.c')
-rw-r--r--min_num_ops_sort_bt.c89
1 files changed, 89 insertions, 0 deletions
diff --git a/min_num_ops_sort_bt.c b/min_num_ops_sort_bt.c
new file mode 100644
index 0000000..1f42594
--- /dev/null
+++ b/min_num_ops_sort_bt.c
@@ -0,0 +1,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);
+}