aboutsummaryrefslogtreecommitdiff
path: root/leaf_similar_trees.rs
blob: 6dcaae1b25005df2c5262b2c081aa170876ff6e5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None
        }
    }
}

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn leaf_similar(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let mut leaves1 = Vec::<i32>::new();
        Solution::get_leaves(root1, &mut leaves1);
        let mut leaves2 = Vec::<i32>::new();
        Solution::get_leaves(root2, &mut leaves2);
        leaves1 == leaves2
    }
    fn get_leaves(node: Option<Rc<RefCell<TreeNode>>>, leaves: &mut Vec<i32>) {
        if let Some(node) = node {
            let node = node.borrow();
            if node.left == None && node.right == None {
                leaves.push(node.val);
            } else {
                if let Some(ref left_node) = node.left {
                    Solution::get_leaves(Some(Rc::clone(left_node)), leaves);
                }
                if let Some(ref right_node) = node.right {
                    Solution::get_leaves(Some(Rc::clone(right_node)), leaves);
                }
            }
        }
    }
}