剑指Offer——对成的二叉树

1、题目描述

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

2、代码实现

/*
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)
    {
        //1、边界检测：空树是对称的
        if (pRoot == null) {
            return true;
        }
        //2、先求出该树的镜像树
        TreeNode root = Mirror(pRoot);
        //3、把两棵树的比较结果进行返回，两棵树相同返回true，两棵树不相同返回false
        return isSymmetrical(pRoot, root);
    }
    //这个函数就是比较给定的两棵树是否相等的
     private boolean isSymmetrical(TreeNode pRoot, TreeNode root) {
         //边界值检测：如果两棵树都为空则两棵树是一样的，如果两棵树只有其中一棵树为空，那么两棵树
         //是不对称的
        if (root == null && pRoot == null) {
            return true;
        } else if (root == null || pRoot == null) {
            return false;
        }
         //边界值检测完毕比较两棵树的根结点值是否相等，如果相等，在递归的比较两棵树的左子树和右子树是否相等
        if (root.val == pRoot.val) {
            return isSymmetrical(root.left, pRoot.left) && isSymmetrical(root.right, pRoot.right);
        }
        return false;

    }
    //这个函数的作用就是求出给定根节点对应树的镜像树
    private TreeNode Mirror(TreeNode root) {
        if (root == null) {
            return null;
        }
        //创建一个新的根节点，然后把原根节点的左子树赋值给新创建根节点的右子树
        //把原根节点的右子树赋值给新创建根节点的左子树，最后返回新创建的根节点即可
        TreeNode tempRoot = new TreeNode(root.val);
        tempRoot.left = Mirror(root.right);
        tempRoot.right = Mirror(root.left);
        return tempRoot;
    }
}