5.5SymmetricTree - WisperDin/blog GitHub Wiki

Description

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

Note: Bonus points if you could solve it both recursively and iteratively.

前言

我一开始犯了一个比较蠢的错误，就是想用中序表达式是否回文来判断，但后面提交出错后猛然回想起了数据结构老师说过的一句话，仅凭着 前序/中序/后序 表达式 的其中一个表达式是无法确定一个二叉树的

思路

要判定一棵二叉树是否以中线对称，可以通过一直往下比较子树的方法，即一棵二叉树的左子树如果和右子树为镜像对称，则称该二叉树对称

A，B 镜像对称：A ，B的根节点的值一样，A的左子树和B的右子树镜像对称，A的右子树和B的左子树镜像对称

实现

递归实现：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root)
            return true;
        return isMirror(root->left,root->right);
    }
private: bool isMirror(TreeNode* left,TreeNode* right){
    if (!left && !right)
        return true;
     if (!left || !right)
        return false;
    if (left->val != right->val)
        return false;
    if (!isMirror(left->left,right->right))
        return false;
    if (!isMirror(left->right,right->left))
        return false;
    return true;
} 
};

迭代实现：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
       queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty()){
            TreeNode* t1 = q.front();
            q.pop();
            TreeNode* t2 = q.front();
            q.pop();
            if (!t1 && !t2) continue;
            if (!t1 || !t2) return false;
            if (t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        return true;
    }
};
⚠️ **GitHub.com Fallback** ⚠️