use std::cell::RefCell;
use std::rc::Rc;
use std::collections::VecDeque;
pub type TreeLink = Option<Rc<RefCell<TreeNode>>>;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: TreeLink,
pub right: TreeLink,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
pub fn build_tree<const N: usize>(v: [i32; N]) -> TreeLink {
if v.len() == 0 {
None
} else {
let mut stack: VecDeque<TreeLink> = VecDeque::new();
let mut root: TreeLink = None;
for i in v {
match stack.front_mut() {
Some(front) => {
if let Some(node) = front.clone() {
match &mut *node.borrow_mut() {
n @ TreeNode { val: _, left: None, right: None } => {
let new_node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
n.left = new_node.clone();
stack.push_back(new_node);
}
n @ TreeNode { val: _, left: Some(_), right: None } => {
let new_node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
n.right = new_node.clone();
stack.push_back(new_node);
stack.pop_front();
}
_ => panic!("Bitchy at {i}, shouldn't happen!")
}
}
}
None => {
let node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
root = node.clone();
stack.push_back(node);
}
};
}
root
}
}