1
use std::cell::RefCell;
2
use std::rc::Rc;
3
impl Solution {
4
  fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> (i32, Option<Rc<RefCell<TreeNode>>>) {
5
    match root.clone() {
6
      Some(root_ref) => {
7
        let root_node = root_ref.borrow();
8

9
        let (left_height, left_tree) = Self::dfs(&root_node.left);
10
        let (right_height, right_tree) = Self::dfs(&root_node.right);
11

12
        if left_height > right_height {
13
          (left_height + 1, left_tree)
14
        } else if right_height > left_height {
15
          (right_height + 1, right_tree)
16
        } else {
17
          (left_height + 1, root.clone())
18
        }
19
      }
20
      None => (0, None),
21
    }
22
  }
23

24
  pub fn subtree_with_all_deepest(
25
    root: Option<Rc<RefCell<TreeNode>>>,
26
  ) -> Option<Rc<RefCell<TreeNode>>> {
27
    Self::dfs(&root).1
28
  }
29
}