题解 | #对称的二叉树#

最开始尝试直接递归原树进行比较，但是思路有问题。
退而求其次，直接深拷贝原树，再比较两树。
在写比较函数的过程中，我发现之所以最开始原树比较不行，应该是递归函数的比较逻辑出问题了，所以在写完这种方法后继续回头研究原树比较的方法。

/*
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){
            return true;
        }
        TreeNode* cp = new TreeNode(pRoot->val);
        copy(pRoot, cp);
        return mirror(pRoot, cp);
    }
    void copy(TreeNode* p, TreeNode* &np){
        if(p->left){
            TreeNode *temp = new TreeNode(p->left->val);
            np->left = temp;
            copy(p->left, np->left);
        }
        if(p->right){
            TreeNode *temp = new TreeNode(p->right->val);
            np->right = temp;
            copy(p->right, np->right);
        }
    }
    
    bool mirror(TreeNode* p1, TreeNode* p2){
        if(p1->val != p2->val){
            return false;
        }
        if(!p1->left && !p1->right && !p2->left && !p2->right){
            return true;
        }
        if(p1->left && p2->left && p1->right && p2->right){
            return mirror(p1->left, p2->right) && mirror(p1->right, p2->left);
        }
        if(p1->right && p2->left && !p1->left && !p2->right){
            return mirror(p1->right, p2->left);
        }
        if(p1->left && p2->right && !p1->right && !p2->left){
            return mirror(p1->left, p2->right);
        }
        return false;
    }

};

在写完上面那种方法后发现，不需要改动上面写好的比较函数，只需要先对根节点进行判断，然后将根节点的左右节点传入比较函数进行递归比较即可。
这样做省去的深拷贝的成本，时间复杂度和空间复杂度有明显改善。
之所以一开始没有想到这种做法，是因为被根节点的处理迷惑了。开始时在递归中处理根节点，那么递归过程中的子节点必然使用和根节点相同的处理方法，所以出现问题。
吸取这次的教训，在做树的题时，遇到需要比较两树的，可以先单独处理根节点，再把左右两棵子树拿出来做递归比较。

/*
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){
            return true;
        }
        if(!pRoot->left && !pRoot->right){
            return true;
        }
        if(!pRoot->left || !pRoot->right || pRoot->left->val != pRoot->right->val){
            return false;
        }
        return mirror(pRoot->left, pRoot->right);
    }
    bool mirror(TreeNode* p1, TreeNode* p2){
        if(p1->val != p2->val){
            return false;
        }
        if(!p1->left && !p1->right && !p2->left && !p2->right){
            return true;
        }
        if(p1->left && p2->left && p1->right && p2->right){
            return mirror(p1->left, p2->right) && mirror(p1->right, p2->left);
        }
        if(p1->right && p2->left && !p1->left && !p2->right){
            return mirror(p1->right, p2->left);
        }
        if(p1->left && p2->right && !p1->right && !p2->left){
            return mirror(p1->left, p2->right);
        }
        return false;
    }

};