牛客-剑指offer系列题解：对称的二叉树

记录刷题的过程。牛客和力扣中都有相关题目，这里以牛客的题目描述为主。该系列默认采用python语言。

1、问题描述：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

2、所用数据结构：

二叉树

3、题解：

方法1：递归：DFS，
镜像。画出一颗二叉树，把数据认为是一个镜像。如：[2,1,1,5,3,3,5]即是对称的。
python：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        #递归，镜像
        def isMirror(t1, t2):
            if t1 == None and t2 == None:
                return True
            if t1 == None or t2 == None:
                return False
            return (t1.val == t2.val) and isMirror(t1.right, t2.left) and isMirror(t1.left, t2.right)

        return isMirror(root, root)

C++：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode *p,TreeNode *q){
        if (!p && !q)
            return true;
        if (!p || !q)
            return false;
        return p->val == q->val && check(p->left,q->right) &&check(p->right,q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};

方法2：迭代：BFS

python：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root or (not root.left and not root.right):
            return True
        queue = [root.left,root.right]
        while queue:
            left = queue.pop(0)
            right = queue.pop(0)
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            queue.append(left.left)
            queue.append(right.right)
            queue.append(left.right)
            queue.append(right.left)
        return True

C++：

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue<TreeNode*> q;
        q.push(u);q.push(v);
        while(!q.empty()){
            u = q.front();q.pop();
            v = q.front();q.pop();
            if (!u && !v) continue;
            if ((!u || !v) || u->val != v->val) return false;
            q.push(u->left);
            q.push(v->right);
            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};

4、复杂度分析：

方法1和方法2：
时间复杂度：O(N)
空间复杂度：O(N)