剑指offer_【58】对称的二叉树

1.题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

2.解题思路

【分析1】首先我们需要明确一下镜像二叉树的概念，简单来说就是左子树与右子树对调。而根据树的递归定义可以，左子树和右子树的定义也是递归而言的。

【分析2】接下来我们需要明确两棵二叉树什么时候相同。显然，根结点的值相等，左右子树相同，则这两颗二叉树相同。显然，在判断两棵二叉树是否相同时也需要递归地进行判断。

【分析3】根结点对应的值相等，原二叉树Root的左子树与其镜像二叉树Root’的右子树相同，且原二叉树Root的右子树与其镜像二叉树Root’的左子树相同。如此递归下去。直到

① 如果Root和Root'均为空，则返回true；

② 如果Root为空或者Root'为空，则返回false；

③ 如果Root对应的值与Root'对应的值不相等，则返回false。

3.代码

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null || pRoot.left==null&&pRoot.right==null)
            return true;
        return Symmetrical(pRoot.left,pRoot.right);
    }
    boolean Symmetrical(TreeNode left,TreeNode right)
    {
        if(left==null&&right==null)
            return true;
        if(left==null||right==null)
            return false;
        if(left.val==right.val)
                    //右子树的左边跟左子树的右边是否对称

            return    Symmetrical(left.left,right.right)
                   //左子树的右边跟右子树的左边是否对称
                   && Symmetrical(left.right,right.left);

        return false;
            }
}