对称的二叉树

题目的主要信息：

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

轴对称： 非轴对称：

举一反三：

学习完本题的思路你可以解决如下题目：

JZ79. 判断是不是平衡二叉树

JZ55. 二叉树的深度

JZ82. 二叉树中和为某一值的路径(一)

JZ37. 序列化二叉树

JZ27. 二叉树的镜像

方法一：递归（推荐使用）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。

不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序递归可以使用递归：

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

具体做法：

• step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
• step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
• step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。

图示：

Java实现代码：

public class Solution {
    boolean 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);
    }
    boolean isSymmetrical(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }
}

C++实现代码：

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);
    }
};

Python代码实现

class Solution:
    def recursion(self, root1: TreeNode, root2: TreeNode):
        # 可以两个都为空
        if not root1 and not root2: 
            return True
        # 只有一个为空或者节点值不同，必定不对称
        if not root1 or not root2 or root1.val != root2.val:
            return False
        # 每层对应的节点进入递归
        return self.recursion(root1.left, root2.right) and self.recursion(root1.right, root2.left)

    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return self.recursion(pRoot, pRoot)

复杂度分析：

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

方法二：层次遍历（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

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

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

//从左往右加入队列
q1.offer(left.left); 
q1.offer(left.right);
//从右往左加入队列
q2.offer(right.right); 
q2.offer(right.left);

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

具体做法：

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

图示：

Java实现代码：

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        //空树为对称的
        if(pRoot == null) 
            return true;
        //辅助队列用于从两边层次遍历
        Queue<TreeNode> q1 = new LinkedList<TreeNode>(); 
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q1.offer(pRoot.left);
        q2.offer(pRoot.right);
        while(!q1.isEmpty() && !q2.isEmpty()){ 
            //分别从左边和右边弹出节点
            TreeNode left = q1.poll(); 
            TreeNode right = q2.poll();
            //都为空暂时对称
            if(left == null && right == null)
                continue;
            //某一个为空或者数字不相等则不对称
            if(left == null || right == null || left.val != right.val)
                return false;
            //从左往右加入队列
            q1.offer(left.left); 
            q1.offer(left.right);
            //从右往左加入队列
            q2.offer(right.right); 
            q2.offer(right.left);
        }
        //都检验完都是对称的
        return true;
    }
}

C++实现代码：

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; 
    }

};

Python实现代码

import queue
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # 空树为对称的
        if not pRoot: 
            return True
        #辅助队列用于从两边层次遍历
        q1 = queue.Queue() 
        q2 = queue.Queue()
        q1.put(pRoot.left)
        q2.put(pRoot.right)
        while not q1.empty() and not q2.empty(): 
            # 分别从左边和右边弹出节点
            left = q1.get()  
            right = q2.get()
            # 都为空暂时对称
            if not left and not right:
                continue
            # 某一个为空或者数字不相等则不对称
            if not left or not right or left.val != right.val:
                return False
            # 从左往右加入队列
            q1.put(left.left) 
            q1.put(left.right)
            # 从右往左加入队列
            q2.put(right.right) 
            q2.put(right.left)
        # 都检验完都是对称的
        return True 

复杂度分析：

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