description

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? ---

submission

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// 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 {
    // we solve this by iterate through symmertric pair of nodes
    // a pair of symmertric node should have the same value and
    // mirrored children nodes
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let mut nodes = vec![];
        // add the first pair
        if let Some(node) = root {
            let node = node.borrow();
            nodes.push((node.left.clone(), node.right.clone()));
        }
        while let Some((left, right)) = nodes.pop() {
            match (left, right) {
                // both nodes not empty
                (Some(left), Some(right)) => {
                    let left = left.borrow();
                    let right = right.borrow();
                    // check value
                    if left.val != right.val {
                        return false;
                    }
                    // push mirrored children
                    nodes.push((left.left.clone(), right.right.clone()));
                    nodes.push((left.right.clone(), right.left.clone()));
                }
                // both empty, skip
                (None, None) => {}
                // any other case should return false
                _ => return false,
            }
        }
        true
    }
}