-
Notifications
You must be signed in to change notification settings - Fork 2
/
95.unique-binary-search-trees-ii.rs
59 lines (51 loc) · 1.39 KB
/
95.unique-binary-search-trees-ii.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
* @lc app=leetcode id=95 lang=rust
*
* [95] Unique Binary Search Trees II
*/
// @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
fn helper(start: i32, end: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
let mut ans = vec![];
if start > end {
ans.push(None);
return ans;
}
for i in start..end+1 {
for left in helper(start, i-1) {
for right in helper(i+1, end) {
let tree_node = Rc::new(RefCell::new(TreeNode::new(i)));
tree_node.borrow_mut().left = left.clone();
tree_node.borrow_mut().right = right.clone();
ans.push(Some(tree_node));
}
}
}
ans
}
if n == 0 { return vec![]; }
helper(1, n)
}
}
// @lc code=end