LeetCode-in-All
101. Symmetric Tree
Easy
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. -100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Solution
// Definition for a binary tree node.
// 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_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
fn compare(l: Option<Rc<RefCell<TreeNode>>>, r: Option<Rc<RefCell<TreeNode>>>) -> bool {
match (l, r) {
(None, None) => true,
(None, Some(n)) | (Some(n), None) => false,
(Some(l), Some(r)) => {
if l.borrow().val != r.borrow().val {
return false;
}
return compare(l.borrow().left.clone(), r.borrow().right.clone())
&& compare(l.borrow().right.clone(), r.borrow().left.clone())
}
}
}
match root {
Some(r) => compare(r.borrow().left.clone(), r.borrow().right.clone()),
None => true
}
}
}