1932. Merge BSTs to Create Single BST Hard

1/**
2 * [1932] Merge BSTs to Create Single BST
3 *
4 * You are given n BST (binary search tree) root nodes for n separate BSTs stored in an array trees (0-indexed). Each BST in trees has at most 3 nodes, and no two roots have the same value. In one operation, you can:
5 * 
6 * 	Select two distinct indices i and j such that the value stored at one of the leaves of trees[i] is equal to the root value of trees[j].
7 * 	Replace the leaf node in trees[i] with trees[j].
8 * 	Remove trees[j] from trees.
9 * 
10 * Return the root of the resulting BST if it is possible to form a valid BST after performing n - 1 operations, or null if it is impossible to create a valid BST.
11 * A BST (binary search tree) is a binary tree where each node satisfies the following property:
12 * 
13 * 	Every node in the node's left subtree has a value strictly less than the node's value.
14 * 	Every node in the node's right subtree has a value strictly greater than the node's value.
15 * 
16 * A leaf is a node that has no children.
17 *  
18 * Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d1.png" style="width: 450px; height: 163px;" />
20 * Input: trees = [[2,1],[3,2,5],[5,4]]
21 * Output: [3,2,5,1,null,4]
22 * Explanation:
23 * In the first operation, pick i=1 and j=0, and merge trees[0] into trees[1].
24 * Delete trees[0], so trees = [[3,2,5,1],[5,4]].
25 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram.png" style="width: 450px; height: 181px;" />
26 * In the second operation, pick i=0 and j=1, and merge trees[1] into trees[0].
27 * Delete trees[1], so trees = [[3,2,5,1,null,4]].
28 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram-2.png" style="width: 220px; height: 165px;" />
29 * The resulting tree, shown above, is a valid BST, so return its root.
30 * Example 2:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d2.png" style="width: 450px; height: 171px;" />
32 * Input: trees = [[5,3,8],[3,2,6]]
33 * Output: []
34 * Explanation:
35 * Pick i=0 and j=1 and merge trees[1] into trees[0].
36 * Delete trees[1], so trees = [[5,3,8,2,6]].
37 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/24/diagram-3.png" style="width: 240px; height: 196px;" />
38 * The resulting tree is shown above. This is the only valid operation that can be performed, but the resulting tree is not a valid BST, so return null.
39 * 
40 * Example 3:
41 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/d3.png" style="width: 430px; height: 168px;" />
42 * Input: trees = [[5,4],[3]]
43 * Output: []
44 * Explanation: It is impossible to perform any operations.
45 * 
46 *  
47 * Constraints:
48 * 
49 * 	n == trees.length
50 * 	1 <= n <= 5 * 10^4
51 * 	The number of nodes in each tree is in the range [1, 3].
52 * 	Each node in the input may have children but no grandchildren.
53 * 	No two roots of trees have the same value.
54 * 	All the trees in the input are valid BSTs.
55 * 	1 <= TreeNode.val <= 5 * 10^4.
56 * 
57 */
58pub struct Solution {}
59use crate::util::tree::{TreeNode, to_tree};
60
61// problem: https://leetcode.com/problems/merge-bsts-to-create-single-bst/
62// discuss: https://leetcode.com/problems/merge-bsts-to-create-single-bst/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66// Definition for a binary tree node.
67// #[derive(Debug, PartialEq, Eq)]
68// pub struct TreeNode {
69//   pub val: i32,
70//   pub left: Option<Rc<RefCell<TreeNode>>>,
71//   pub right: Option<Rc<RefCell<TreeNode>>>,
72// }
73// 
74// impl TreeNode {
75//   #[inline]
76//   pub fn new(val: i32) -> Self {
77//     TreeNode {
78//       val,
79//       left: None,
80//       right: None
81//     }
82//   }
83// }
84use std::rc::Rc;
85use std::cell::RefCell;
86impl Solution {
87    pub fn can_merge(trees: Vec<Option<Rc<RefCell<TreeNode>>>>) -> Option<Rc<RefCell<TreeNode>>> {
88        Some(Rc::new(RefCell::new(TreeNode::new(0))))
89    }
90}
91
92// submission codes end
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97
98    #[test]
99    fn test_1932() {
100    }
101}
102