leetcode_tree/
lib.rs

1use std::cell::RefCell;
2use std::rc::Rc;
3use std::collections::VecDeque;
4
5pub type TreeLink = Option<Rc<RefCell<TreeNode>>>;
6
7#[derive(Debug, PartialEq, Eq)]
8pub struct TreeNode {
9    pub val: i32,
10    pub left: TreeLink,
11    pub right: TreeLink,
12}
13
14impl TreeNode {
15    #[inline]
16    pub fn new(val: i32) -> Self {
17        TreeNode {
18            val,
19            left: None,
20            right: None,
21        }
22    }
23}
24
25
26pub fn build_tree<const N: usize>(v: [i32; N]) -> TreeLink {
27    if v.len() == 0 {
28        None
29    } else {
30        let mut stack: VecDeque<TreeLink> = VecDeque::new();
31        let mut root: TreeLink = None;
32
33        for i in v {
34            match stack.front_mut() {
35                Some(front) => {
36                    if let Some(node) = front.clone() {
37                        match &mut *node.borrow_mut() {
38                            n @ TreeNode { val: _, left: None, right: None } => {
39                                let new_node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
40                                n.left = new_node.clone();
41                                stack.push_back(new_node);
42                            }
43                            n @ TreeNode { val: _, left: Some(_), right: None } => {
44                                let new_node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
45                                n.right = new_node.clone();
46                                stack.push_back(new_node);
47                                stack.pop_front();
48                            }
49                            _ => panic!("Bitchy at {i}, shouldn't happen!")
50                        }
51                    }
52                }
53                None => {
54                    let node: TreeLink = Some(Rc::new(RefCell::new(TreeNode::new(i))));
55                    root = node.clone();
56                    stack.push_back(node);
57                }
58            };
59        }
60        root
61    }
62}
63
leetcode_tree/lib.rs

leetcode_tree/
lib.rs
