aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-23 11:14:31 -0700
committerJack Sangdahl <[email protected]>2024-12-23 11:14:31 -0700
commitf124090178e245d8c091689067bf3f566c20781b (patch)
tree8d09ed5f083c178893127f70ef5761d07923ea15
parent54f080060fcc02331855b1958bd371f9769d35da (diff)
downloadleetcode-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.c89
-rw-r--r--min_num_ops_sort_bt.py64
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]))