题解 | #对称的二叉树#

方法一（递归）

1.题意整理

• 给定一颗二叉树。
• 判断其是否是自己的镜像。

2.思路整理

首先考虑二叉树是否为空，如果为空，则说明是对称的，直接返回true。否则递归地判断左右子树是否是对称的。

• 递归终止条件：如果左右子树同时为空，说明所有子树都满足要求，返回true。如果左子树为空，右子树不为空或者右子树为空，左子树不为空，说明不满足对称要求，返回false。
• 递归如何传递：每次递归，都要比较当前节点root1和root2相等，同时比较root1左子节点是否等于root2右子节点，root1右子节点是否等于root2左子节点。
• 递归的返回值：返回当前层节点是否符合对称的要求。

图解展示：

3.代码实现

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        //如果为空，说明是对称的
        if(pRoot==null) return true;
        return check(pRoot.left,pRoot.right);
    }
    
    boolean check(TreeNode root1,TreeNode root2){
        //如果左右子树同时为空，说明所有子树都满足要求，返回true
        if(root1==null&&root2==null) return true;
        //左子树为空，右子树不为空或者右子树为空，左子树不为空，说明不满足对称要求
        if(root1==null||root2==null) return false;
        //每次递归，要求当前节点相等，同时root1左子节点等于root2右子节点，root1右子节点等于root2左子节点
        return root1.val==root2.val&&check(root1.left,root2.right)&&check(root1.right,root2.left);
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有的节点，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外深度为n的递归栈开销，所以空间复杂度为$O(n)O(n)$。