101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3]
is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following [1,2,2,null,3,null,3]
is not:
1 / \ 2 2 \ \ 3 3
Follow up: Solve it both recursively and iteratively.
Rust Solution
struct Solution;
use rustgym_util::*;
trait Symmetric {
fn is_symmetric(&self) -> bool;
fn is_mirror(&self, right: &TreeLink) -> bool;
}
impl Symmetric for TreeLink {
fn is_symmetric(&self) -> bool {
if let Some(node) = self {
let node = node.borrow();
node.left.is_mirror(&node.right)
} else {
true
}
}
fn is_mirror(&self, right: &TreeLink) -> bool {
match (self, right) {
(Some(p), Some(q)) => {
let p = p.borrow();
let q = q.borrow();
p.val == q.val && p.left.is_mirror(&q.right) && p.right.is_mirror(&q.left)
}
(None, None) => true,
_ => false,
}
}
}
impl Solution {
fn is_symmetric(root: TreeLink) -> bool {
root.is_symmetric()
}
}
#[test]
fn test() {
let q = tree!(
1,
tree!(2, tree!(1), tree!(1)),
tree!(2, tree!(1), tree!(1))
);
assert_eq!(Solution::is_symmetric(q), true)
}
Having problems with this solution? Click here to submit an issue on github.