669. Trim a Binary Search Tree Medium

1/**
2 * [669] Trim a Binary Search Tree
3 *
4 * Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.
5 * Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/09/trim1.jpg" style="width: 450px; height: 126px;" />
9 * Input: root = [1,0,2], low = 1, high = 2
10 * Output: [1,null,2]
11 * 
12 * Example 2:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/09/trim2.jpg" style="width: 450px; height: 277px;" />
14 * Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
15 * Output: [3,2,null,1]
16 * 
17 *  
18 * Constraints:
19 * 
20 * 	The number of nodes in the tree is in the range [1, 10^4].
21 * 	0 <= Node.val <= 10^4
22 * 	The value of each node in the tree is unique.
23 * 	root is guaranteed to be a valid binary search tree.
24 * 	0 <= low <= high <= 10^4
25 * 
26 */
27pub struct Solution {}
28use crate::util::tree::{TreeNode, to_tree};
29
30// problem: https://leetcode.com/problems/trim-a-binary-search-tree/
31// discuss: https://leetcode.com/problems/trim-a-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35// Definition for a binary tree node.
36// #[derive(Debug, PartialEq, Eq)]
37// pub struct TreeNode {
38//   pub val: i32,
39//   pub left: Option<Rc<RefCell<TreeNode>>>,
40//   pub right: Option<Rc<RefCell<TreeNode>>>,
41// }
42// 
43// impl TreeNode {
44//   #[inline]
45//   pub fn new(val: i32) -> Self {
46//     TreeNode {
47//       val,
48//       left: None,
49//       right: None
50//     }
51//   }
52// }
53use std::rc::Rc;
54use std::cell::RefCell;
55impl Solution {
56    pub fn trim_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> Option<Rc<RefCell<TreeNode>>> {
57        Some(Rc::new(RefCell::new(TreeNode::new(0))))
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_669() {
69    }
70}
71