binarytree/
lib.rs

1//! Rust :: Binary Tree
2
3use std::cell::RefCell;
4use std::rc::Rc;
5
6#[derive(Debug, PartialEq, Eq)]
7pub struct TreeNode {
8    pub val: i32,
9    pub left: Option<Rc<RefCell<TreeNode>>>,
10    pub right: Option<Rc<RefCell<TreeNode>>>,
11}
12
13impl TreeNode {
14    #[inline]
15    pub fn new(val: i32) -> Self {
16        TreeNode {
17            val,
18            left: None,
19            right: None,
20        }
21    }
22}
23
24/// 1123m Lowest Common Ancestor of Deepest Leaves
25struct Sol1123;
26
27impl Sol1123 {
28    pub fn lca_deepest_leaves(
29        root: Option<Rc<RefCell<TreeNode>>>,
30    ) -> Option<Rc<RefCell<TreeNode>>> {
31        fn dfs(n: Option<Rc<RefCell<TreeNode>>>) -> (i32, Option<Rc<RefCell<TreeNode>>>) {
32            println!("-> {:?}", n);
33
34            match n {
35                None => (0, None),
36                Some(n) => {
37                    let nref = n.borrow();
38                    let (ld, l) = dfs(nref.left.clone());
39                    let (rd, r) = dfs(nref.right.clone());
40
41                    use std::cmp::Ordering::*;
42                    match ld.cmp(&rd) {
43                        Less => (1 + rd, r),
44                        Greater => (1 + ld, l),
45                        Equal => (1 + (ld | rd), Some(n.clone())),
46                    }
47                }
48            }
49        }
50
51        dfs(root).1
52    }
53}
54
55/// 2236 Root Equals Sum of Children
56struct Sol2236 {}
57
58impl Sol2236 {
59    pub fn check_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
60        let root = root.unwrap();
61        let n = root.borrow();
62        let l = n.left.as_ref().unwrap().borrow();
63        let r = n.right.as_ref().unwrap().borrow();
64
65        n.val == l.val + r.val
66    }
67}
68
69#[cfg(test)]
70mod tests;
binarytree/lib.rs

binarytree/
lib.rs
