a0894_all_possible_full_binary_trees.rs

/*
 * [0894] all-possible-full-binary-trees
 */

usesuper::utils::tree::*;
structSolution;

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
implSolution{
pubfnall_possible_fbt(n:i32) -> Vec<Option<Rc<RefCell<TreeNode>>>>{
letmut m:HashMap<i32,Vec<Option<Rc<RefCell<TreeNode>>>>> = HashMap::new();
Self::get(n,&mut m)
}

fnget(
n:i32,
m:&mutHashMap<i32,Vec<Option<Rc<RefCell<TreeNode>>>>>,
) -> Vec<Option<Rc<RefCell<TreeNode>>>>{
if !m.contains_key(&n){
letmut ans = Vec::new();
if n == 1{
 ans.push(Some(Rc::new(RefCell::new(TreeNode{
left:Option::None,
right:Option::None,
val:0,
}))));
}elseif n % 2 == 1{
for x in0..n {
let y = n - 1 - x;
for left inSelf::all_possible_fbt(x){
for right inSelf::all_possible_fbt(y){
let n = Some(Rc::new(RefCell::new(TreeNode{
left: left.clone(),
right: right.clone(),
val:0,
})));
 ans.push(n);
}
}
}
}
 m.insert(n, ans);
}
 m.get(&n).unwrap().to_vec()
}
}

#[cfg(test)]
mod tests {
usesuper::*;

#[test]
fntest_case0(){
assert_eq!(Solution::all_possible_fbt(1), vec![tree![0]]);
assert_eq!(
Solution::all_possible_fbt(7),
 vec![
 tree![0,0,0, null, null,0,0, null, null,0,0],
 tree![0,0,0, null, null,0,0,0,0],
 tree![0,0,0,0,0,0,0],
 tree![0,0,0,0,0, null, null, null, null,0,0],
 tree![0,0,0,0,0, null, null,0,0]
]
);
}
}