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.