对称的二叉树

---

题目描述

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

解题思路

判断是否是对称二叉树，即需遍历二叉树输出的序列与二叉树的镜像输出序列进行对比，若相同即为对称二叉树。

问题就是怎样得到二叉树的镜像？

无论是前序遍历、中序遍历、后序遍历，它们的特点是先遍历左树再遍历右树。因此为了获得二叉树的镜像，则只需在遍历的时候先遍历右树再遍历左树即可。

图一：前序遍历的输出序列是：8657765；镜像遍历：8657765；两个输出序列相同则认定为对称二叉树。

图二：前序遍历的输出序列是：8657795；镜像遍历：8957765；两个输出序列不同，则不是对称二叉树。

图三：前序遍历的输出序列是：77777；镜像遍历：777777；单从输出序列上看，判断是对称二叉树，但是从给的树的形状上看明显不是对称二叉树。

通过观察发现，在前序遍历的过程中习惯把NULL省略。为了确保对于所有结点都相等的二叉树有效，所以在遍历的过程中需要将NULL也要输出。

图三：前序遍历的输出：777777NULL; 镜像遍历：77NULL7777.两个输出序列不同，则不是对称二叉树。

代码

struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode (int x): val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    bool isSymmetrical (TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return true;
        return isSymmetricalCore(pRoot, pRoot);
    }
private:
    bool isSymmetricalCore (TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if (pRoot1 == NULL && pRoot2 == NULL)
            return true;
        if (pRoot1 == NULL || pRoot2 == NULL)
            return false;
        if (pRoot1->val != pRoot2->val)
            return false;
        return isSymmetricalCore(pRoot1->left, pRoot2->right) && isSymmetricalCore(pRoot1->right, pRoot2->left);
    }
};

参考链接：https://cuijiahua.com/blog/2018/01/basis_58.html