diff options
author | Jack Sangdahl <[email protected]> | 2024-12-23 11:14:31 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-23 11:14:31 -0700 |
commit | f124090178e245d8c091689067bf3f566c20781b (patch) | |
tree | 8d09ed5f083c178893127f70ef5761d07923ea15 | |
parent | 54f080060fcc02331855b1958bd371f9769d35da (diff) | |
download | leetcode-f124090178e245d8c091689067bf3f566c20781b.tar.gz leetcode-f124090178e245d8c091689067bf3f566c20781b.zip |
2471. minimum number of operations to sort a binary tree by level
-rw-r--r-- | min_num_ops_sort_bt.c | 89 | ||||
-rw-r--r-- | min_num_ops_sort_bt.py | 64 |
2 files changed, 153 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); +} diff --git a/min_num_ops_sort_bt.py b/min_num_ops_sort_bt.py new file mode 100644 index 0000000..987aefa --- /dev/null +++ b/min_num_ops_sort_bt.py @@ -0,0 +1,64 @@ +# 2471. Minimum Number of Operations to Sort a Binary Tree by Level +from collections import deque + +""" +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. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def minimumOperations(self, root): + """ + :type root: Optional[TreeNode] + :rtype: int + """ + + def dfs(i, idx, seen): + if seen[i]: + return 0 + seen[i] = True + j = idx[i] + return dfs(j, idx, seen) + 1 + + q = deque() + q.append(root) + swaps = 0 + while q: + n = len(q) + arr = [0] * n + for i in range(n): + node = q.popleft() + arr[i] = node.val + if node.left: + q.append(node.left) + if node.right: + q.append(node.right) + idx = sorted(range(n), key=lambda x: arr[x]) + seen = [False] * n + for i in range(n): + if not seen[i]: + swaps += dfs(i, idx, seen) - 1 + return swaps + + +if __name__ == "__main__": + obj = Solution() + print( + obj.minimumOperations( + root=[1, 4, 3, 7, 6, 8, 5, None, None, None, None, 9, None, 10] + ) + ) + print(obj.minimumOperations(root=[1, 3, 2, 7, 6, 5, 4])) + print(obj.minimumOperations(root=[1, 2, 3, 4, 5, 6])) |