diff options
Diffstat (limited to 'min_num_ops_sort_bt.c')
-rw-r--r-- | min_num_ops_sort_bt.c | 89 |
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); +} |