1382. Balance a Binary Search Tree Medium

1/**
2 * [1382] Balance a Binary Search Tree
3 *
4 * Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.
5 * A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/balance1-tree.jpg" style="width: 500px; height: 319px;" />
9 * Input: root = [1,null,2,null,3,null,4,null,null]
10 * Output: [2,1,3,null,null,null,4]
11 * Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/balanced2-tree.jpg" style="width: 224px; height: 145px;" />
15 * Input: root = [2,1,3]
16 * Output: [2,1,3]
17 * 
18 *  
19 * Constraints:
20 * 
21 * 	The number of nodes in the tree is in the range [1, 10^4].
22 * 	1 <= Node.val <= 10^5
23 * 
24 */
25pub struct Solution {}
26use crate::util::tree::{TreeNode, to_tree};
27
28// problem: https://leetcode.com/problems/balance-a-binary-search-tree/
29// discuss: https://leetcode.com/problems/balance-a-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
30
31// submission codes start here
32
33// Definition for a binary tree node.
34// #[derive(Debug, PartialEq, Eq)]
35// pub struct TreeNode {
36//   pub val: i32,
37//   pub left: Option<Rc<RefCell<TreeNode>>>,
38//   pub right: Option<Rc<RefCell<TreeNode>>>,
39// }
40// 
41// impl TreeNode {
42//   #[inline]
43//   pub fn new(val: i32) -> Self {
44//     TreeNode {
45//       val,
46//       left: None,
47//       right: None
48//     }
49//   }
50// }
51use std::rc::Rc;
52use std::cell::RefCell;
53impl Solution {
54    pub fn balance_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
55        Some(Rc::new(RefCell::new(TreeNode::new(0))))
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_1382() {
67    }
68}
69