95. Unique Binary Search Trees II Medium

1/**
2 * [95] Unique Binary Search Trees II
3 *
4 * Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg" style="width: 600px; height: 148px;" />
8 * Input: n = 3
9 * Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
10 *
11 * Example 2:
12 *
13 * Input: n = 1
14 * Output: [[1]]
15 *
16 *  
17 * Constraints:
18 *
19 * 1 <= n <= 8
20 *
21 */
22pub struct Solution {}
23#[allow(unused_imports)]
24use crate::util::tree::{to_tree, TreeNode};
25
26// problem: https://leetcode.com/problems/unique-binary-search-trees-ii/
27// discuss: https://leetcode.com/problems/unique-binary-search-trees-ii/discuss/?currentPage=1&orderBy=most_votes&query=
28
29// submission codes start here
30
31// Definition for a binary tree node.
32// #[derive(Debug, PartialEq, Eq)]
33// pub struct TreeNode {
34//   pub val: i32,
35//   pub left: Option<Rc<RefCell<TreeNode>>>,
36//   pub right: Option<Rc<RefCell<TreeNode>>>,
37// }
38//
39// impl TreeNode {
40//   #[inline]
41//   pub fn new(val: i32) -> Self {
42//     TreeNode {
43//       val,
44//       left: None,
45//       right: None
46//     }
47//   }
48// }
49use std::cell::RefCell;
50use std::rc::Rc;
51
52type Node = Option<Rc<RefCell<TreeNode>>>;
53impl Solution {
54    pub fn generate_trees(n: i32) -> Vec<Node> {
55        if n == 0 {
56            return vec![];
57        }
58
59        Self::generate(1, n as usize)
60    }
61
62    fn generate(start: usize, end: usize) -> Vec<Node> {
63        let mut trees = vec![];
64        if start > end {
65            trees.push(None);
66            return trees;
67        }
68
69        for i in start..=end {
70            let left = Self::generate(start, i - 1);
71            let right = Self::generate(i + 1, end);
72
73            for j in left.iter() {
74                for k in right.iter() {
75                    let mut root = TreeNode::new(i as i32);
76                    root.left = j.clone();
77                    root.right = k.clone();
78
79                    trees.push(Some(Rc::new(RefCell::new(root))));
80                }
81            }
82        }
83        trees
84    }
85}
86
87// submission codes end
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_95() {
95        println!("Got {:#?}", Solution::generate_trees(5));
96    }
97}
98