2471. Minimum Number of Operations to Sort a Binary Tree by Level Medium

1/**
2 * [2471] Minimum Number of Operations to Sort a Binary Tree by Level
3 *
4 * You are given the root of a binary tree with unique values.
5 * In one operation, you can choose any two nodes at the same level and swap their values.
6 * Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order.
7 * The level of a node is the number of edges along the path between it and the root node.
8 *  
9 * <strong class="example">Example 1:
10 * <img src="https://assets.leetcode.com/uploads/2022/09/18/image-20220918174006-2.png" style="width: 500px; height: 324px;" />
11 * Input: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
12 * Output: 3
13 * Explanation:
14 * - Swap 4 and 3. The 2^nd level becomes [3,4].
15 * - Swap 7 and 5. The 3^rd level becomes [5,6,8,7].
16 * - Swap 8 and 7. The 3^rd level becomes [5,6,7,8].
17 * We used 3 operations so return 3.
18 * It can be proven that 3 is the minimum number of operations needed.
19 * 
20 * <strong class="example">Example 2:
21 * <img src="https://assets.leetcode.com/uploads/2022/09/18/image-20220918174026-3.png" style="width: 400px; height: 303px;" />
22 * Input: root = [1,3,2,7,6,5,4]
23 * Output: 3
24 * Explanation:
25 * - Swap 3 and 2. The 2^nd level becomes [2,3].
26 * - Swap 7 and 4. The 3^rd level becomes [4,6,5,7].
27 * - Swap 6 and 5. The 3^rd level becomes [4,5,6,7].
28 * We used 3 operations so return 3.
29 * It can be proven that 3 is the minimum number of operations needed.
30 * 
31 * <strong class="example">Example 3:
32 * <img src="https://assets.leetcode.com/uploads/2022/09/18/image-20220918174052-4.png" style="width: 400px; height: 274px;" />
33 * Input: root = [1,2,3,4,5,6]
34 * Output: 0
35 * Explanation: Each level is already sorted in increasing order so return 0.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	The number of nodes in the tree is in the range [1, 10^5].
41 * 	1 <= Node.val <= 10^5
42 * 	All the values of the tree are unique.
43 * 
44 */
45pub struct Solution {}
46use crate::util::tree::{TreeNode, to_tree};
47
48// problem: https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/
49// discuss: https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53// Definition for a binary tree node.
54// #[derive(Debug, PartialEq, Eq)]
55// pub struct TreeNode {
56//   pub val: i32,
57//   pub left: Option<Rc<RefCell<TreeNode>>>,
58//   pub right: Option<Rc<RefCell<TreeNode>>>,
59// }
60// 
61// impl TreeNode {
62//   #[inline]
63//   pub fn new(val: i32) -> Self {
64//     TreeNode {
65//       val,
66//       left: None,
67//       right: None
68//     }
69//   }
70// }
71use std::rc::Rc;
72use std::cell::RefCell;
73impl Solution {
74    pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
75        0
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_2471() {
87    }
88}
89