Same tree

Tree Depth-First Search Breadth-First Search Binary Tree

66.7% acceptance

Feb 27, 2026

12803

299

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// 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 is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
    match (p, q) {
      (None, None) => true,
      (None, Some(_)) | (Some(_), None) => false,
      (Some(p_node), Some(q_node)) => {
        let p_borrow = p_node.borrow();
        let q_borrow = q_node.borrow();
        p_borrow.val == q_borrow.val
          && Self::is_same_tree(p_borrow.left.clone(), q_borrow.left.clone())
          && Self::is_same_tree(p_borrow.right.clone(), q_borrow.right.clone())
      }
    }
  }
}