1
2
3
4
5

    1
   / \
  2   2
 / \ / \
3  4 4  3

1
2
3
4
5

    1
   / \
  2   2
   \   \
   3    3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

// @lc code=start
// 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::cell::RefCell;
use std::rc::Rc;
impl Solution {
    /// ## 迭代
    pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let root = &root;
        if let Some(node) = root {
            let mut q = vec![];
            q.push(node.borrow().left.clone());
            q.push(node.borrow().right.clone());
            while !q.is_empty() {
                match (q.pop(), q.pop()) {
                    (Some(a), Some(b)) => match (a, b) {
                        (Some(a), Some(b)) => {
                            if a.borrow().val != b.borrow().val {
                                return false;
                            } else {
                                q.push(a.borrow().left.clone());
                                q.push(b.borrow().right.clone());
                                q.push(a.borrow().right.clone());
                                q.push(b.borrow().left.clone());
                            }
                        }
                        (None, None) => {}
                        _ => return false,
                    },
                    (None, None) => return true,
                    _ => return false,
                }
            }

            return true;
        } else {
            return true;
        }
    }

    /// ## 递归
    pub fn is_symmetric2(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        /// a, b是否为镜像树
        fn is_mirror(a: &Option<Rc<RefCell<TreeNode>>>, b: &Option<Rc<RefCell<TreeNode>>>) -> bool {
            match (a, b) {
                (None, None) => true,
                (Some(a), Some(b)) => {
                    a.borrow().val == b.borrow().val
                        && is_mirror(&a.borrow().left, &b.borrow().right)
                        && is_mirror(&a.borrow().right, &b.borrow().left)
                }
                _ => false,
            }
        }

        match root {
            None => true,
            Some(root) => is_mirror(&root.borrow().left, &root.borrow().right),
        }
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    /*
    ## 解题思路
    * * 解法一：递归法
    * * 转化为镜像树问题；
    * * 镜像子树：根节点相等 且 相互的左子树，右子树互为镜像子树；
    */
    bool isSymmetric(TreeNode* root) {
        return isMirrorByRec(root, root);
        //return isMirrorByIter(root, root);
    }

    // check p,q is mirror
    bool isMirrorByRec(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return (p->val == q->val
            && isMirrorByRec(p->left, q->right)
            && isMirrorByRec(p->right, q->left)
        ) ;
    }
    /*
    ## 解法二：迭代法
       * 使用一个队列层历该树；
       * 初始将root入队两次；
       * 然后每次队列出队时，
    */
    bool isMirrorByIter(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;

        queue<TreeNode*> queue;
        queue.push(p);
        queue.push(q);
        while(!queue.empty()) {
            p = queue.front(); queue.pop();
            q = queue.front(); queue.pop();
            if (!p && !q) continue;
            if (!p || !q) return false;
            if (p->val != q->val) return false;
            queue.push(p->left);
            queue.push(q->right);
            queue.push(p->right);
            queue.push(q->left);
        }

        return true;
    }

};