题解 | #对称的二叉树#

题目的主要信息：

判断一棵二叉树是否是镜像，即判断二叉树是否是轴对称图形

轴对称： alt 非轴对称： alt

方法一：递归

具体做法：

前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。依据前序递归的次序，我们先访问根节点，然后递归地进入左子节点和右子节点，如果要采用“根右左”的顺序，那就应该是递归地进入右子节点，然后进入左子节点。我们可以准备两个指针啊，遍历的时候“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，这样刚好可以同步遍历比较。

终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
返回值： 每一级将子问题是否匹配的结果往上传递。
本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。

class Solution {
public:
    bool recursion(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL && root2 == NULL) //可以两个都为空
            return true;
        if(root1 == NULL || root2 == NULL || root1->val != root2->val) //只有一个为空或者节点值不同，必定不对称
            return false;
        return recursion(root1->left, root2->right) && recursion(root1->right, root2->left); //每层对应的节点
    }
    bool isSymmetrical(TreeNode* pRoot) {
        return recursion(pRoot, pRoot);
    }

};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，相当于遍历整个二叉树两次
空间复杂度： $O (n)$ ，最坏情况二叉树退化为链表，递归栈深度为 $n$

方法二：层次遍历

具体做法：

除了递归以外，我们还可以观察，对称的二叉树每一层都是回文的情况，即两边相互对应相等，有节点值的对应节点值，没有节点的连空节点都是对应着的呢。那我们从左往右遍历一层（包括空节点），和从右往左遍历一层（包括空节点），是不是就是得到一样的结果了。（注：必须包含空节点，因为空节点乱插入会导致不同，如题干第二个图所示）。

这时候二叉树每一层的遍历，我就需要用到了层次遍历。层次遍历从左往右经过第一层后，怎么进入第二层？我们可以借助队列——一个先进先出的容器，在遍历第一层的时候，将第一层节点的左右节点都加入到队列中，因为加入队列的顺序是遍历的顺序且先左后右，也就导致了我从队列出来的时候也是下一层的先左后右，正好一一对应。更巧的是，如果我们要从右到左遍历一层，加入队列后也是先右后左，简直完美对应！

而且我们不需要两个层次遍历都完整地遍历二叉树，只需要一半就行了，从左往右遍历左子树，从右往左遍历右子树，各自遍历一半相互比对，因为遍历到另一半都已经检查过了。

step 1：首先判断链表是否为空，空链表直接就是对称。
step 2：准备两个队列，分别作为从左往右层次遍历和从右往左层次遍历的辅助容器，初始第一个队列加入左节点，第二个队列加入右节点。
step 3：循环中每次从队列分别取出一个节点，如果都为空，暂时可以说是对称的，进入下一轮检查；如果某一个为空或是两个节点值不同，那必定不对称。其他情况暂时对称，可以依次从左往右加入子节点到第一个队列，从右往左加入子节点到第二个队列。（这里包括空节点）
step 4：遍历结束也没有检查到不匹配，说明就是对称的。

具体图示可以参考如下：

alt

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot == NULL) //空链表为对称的
            return true;
        queue<TreeNode*> q1; //辅助队列用于从两边层次遍历
        queue<TreeNode*> q2;
        q1.push(pRoot->left);
        q2.push(pRoot->right);
        while(!q1.empty() && !q2.empty()){ 
            TreeNode* left = q1.front(); //分别从左边和右边弹出节点
            q1.pop();
            TreeNode* right = q2.front();
            q2.pop();
            if(left == NULL && right == NULL) //都为空暂时对称
                continue;
            if(left == NULL || right == NULL || left->val != right->val) //某一个为空或者数字不相等则不对称
                return false;
            q1.push(left->left); //从左往右加入队列
            q1.push(left->right);
            q2.push(right->right); //从右往左加入队列
            q2.push(right->left);
        }
        return true; //都检验完都是对称的
    }

};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点个数，相当于遍历二叉树全部节点
空间复杂度： $O (n)$ ，两个辅助队列的最大空间为 $n$