aboutsummaryrefslogtreecommitdiff
path: root/min_num_ops_sort_bt.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_num_ops_sort_bt.py')
-rw-r--r--min_num_ops_sort_bt.py64
1 files changed, 64 insertions, 0 deletions
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]))