872. Leaf-Similar Trees

Description of Problem

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Constraints:

The number of nodes in each tree will be in the range [1, 200].
Both of the given trees will have values in the range [0, 200].

Solution

Tags: Binary Tree DFS

Explanation

Append the node value when the node is leaf.

Code

// Definition for a binary tree node.
// #[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 v1 = vec![];
        let mut v2 = vec![];
        Self::dfs(root1, &mut v1); 
        Self::dfs(root2, &mut v2);
        return v1==v2;
    }

    fn dfs(node: Option<Rc<RefCell<TreeNode>>>, v : &mut Vec<i32> ) {
        if let Some(n) = node.clone() {
            let n = n.borrow();
            let left = n.left.clone();
            let right = n.right.clone();
            
            if left.is_none() && right.is_none(){
                v.push(n.val);
            }else {
                Self::dfs(left, v);
                Self::dfs(right, v);
            }
        }
    }
}

Complexity

n is the number of nodes in the tree
h is the height of the tree

Time complexity:

\( T(n) = \Theta(n) \)

Auxiliary Space:

\( S(n) = O(h) \)

Leetbook