题解 | #对称的二叉树#

描述

定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

例如：
对称的

不对称

要求：空间复杂度 O(n)，时间复杂度 O(n)

备注：你可以用递归和迭代两种方法解决这个问题

解法一：递归

子树对称条件：

• 根节点相同
• 左子树的左子树 和 右子树的右子树对称
• 右子树的左子树 和 左子树的右子树对称

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {

        if (pRoot == null) {
            return true;
        }
        // 定义一个方法，判断左右子树是否镜像对称
        return mirror(pRoot.left, pRoot.right);
    }

    public boolean mirror(TreeNode left, TreeNode right) {
        // 1.如果左树和右边为空
        if (left == null && right == null) {
            return true;
        }

        // 2.如果左树或者右树其中一个为空
        if (left == null || right == null) {
            return false;
        }
        
        // 3.如果左右树都不为空
        if(left.val!=right.val){
            return false;
        }
        
        // 4.左右子树为空，且值相等,此时，说明，左右子树均存在，且，left=right。判断子树的子树是否对称
        boolean res =mirror(left.left,right.right)&&mirror(left.right,right.left);
        return res;
    }


}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度O(N)