26.02.2024
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())
})
}