(剑指Offer)对称的二叉树题解

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

题解
虽然本题可以直接无脑爆搜, 但是本着在好打的情况下做到时间复杂度与空间复杂度最优的原则, 此题可以用树的遍历来解. 首先我们要知道, 只要树的先序遍历确定, 树的中序遍历确定, 那么这颗树就是确定的. 所以我们首先求出原树的先序遍历序列, 记为pre, 再求出原树的中序遍历序列, 记为in, 然后把原树做镜像处理, 然后再求出镜像处理之后的树的先序遍历序列, 记为rPre, 然后再求出镜像处理之后的树的中序遍历序列, 记为rIn, 最后再比较一下pre序列与rPre序列是否相同以及in序列与rIn序列是否相同即可. 有任何一个不同则说明这棵树不是对称的.

复杂度分析
由于只有树的遍历操作, 以及树的翻转操作, 所以时间复杂度为O(n), 由于只存储了四个序列, 所以空间复杂度为O(n);
代码:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> pre,in ;
    vector<int> rPre,rIn ;

    void dfs(TreeNode* pRoot,vector<int>&pre,vector<int>&in)
    {
        if(pRoot == NULL) {
            pre.push_back(0x3f3f3f3f) ;
            in.push_back(0x3f3f3f3f) ; 
            ///如果这颗树里的数全是一样的, 那么直接return会有问题, 
            ///这里加入一个inf代表空结点,这样即使数全一样, 得到的遍历序列也会根据树的形态改变而改变
            return ;
        }
        pre.push_back(pRoot -> val) ;
        dfs(pRoot -> left,pre, in) ;
        in.push_back(pRoot -> val) ;
        dfs(pRoot -> right,pre, in) ;
    }

    void rev(TreeNode* pRoot) 
    {
        if(pRoot == NULL) return ;
        rev(pRoot -> left) ;
        rev(pRoot -> right) ;
        swap(pRoot -> left,pRoot -> right) ;
    }

    bool isSymmetrical(TreeNode* pRoot)
    {
        dfs(pRoot,pre,in) ;
        rev(pRoot) ;
        dfs(pRoot,rPre,rIn) ;
        for(int i(0);i<pre.size();++i) {
            if(pre[i] != rPre[i] || in[i] != rIn[i]) return false ;
        }
        return true ;
    }  
};