LeetCode Entry

100. Same Tree

26.02.2024 easy 2024 kotlin rust

Are two binary trees equal?

100. Same Tree easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/519

Problem TLDR

Are two binary trees equal?

Intuition

Use recursion to check current nodes and subtrees.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(log(n))\) for the recursion depth

Code


    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean =
      p?.`val` == q?.`val` && (p == null ||
      isSameTree(p.left, q?.left) &&
      isSameTree(p.right, q?.right))



  pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
    p.as_ref().zip(q.as_ref()).map_or_else(|| p.is_none() && q.is_none(), |(p, q)| {
      let (p, q) = (p.borrow(), q.borrow());
      p.val == q.val &&
      Self::is_same_tree(p.left.clone(), q.left.clone()) &&
      Self::is_same_tree(p.right.clone(), q.right.clone())
    })
  }