剑指offer—对称的二叉树 解答

剑指offer—对称的二叉树

题目描述

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

思路—递归

  • 方法一:获取到该二叉树的镜像,递归判断源二叉树和镜像二叉树是否相等

该方法时间消耗比较大,首先要复制一颗源二叉树(后面需要进行交换操作获得镜像二叉树);第二步就是获取一颗镜像二叉树;第三步就是判断复制的二叉树和镜像二叉树是否相等(递归)

  • 方法二:对称二叉树的左子树和右子树是对称相等的,递归下去,不相等就返回false

根节点的左节点和根节点的右节点值一定相等;左节点的右孩子对应右节点的左孩子,右节点的右孩子对应左节点的左孩子

  • 递归出口

1.当两个节点其中一个节点为空或者两个节点不相等就返回false,说明不满足条件

2.节点都为空就返回true,说明该节点下面没有节点了并且满足相等条件没有退出,这个时候就返回true

  • 递归过程

**那我们只需要从根节点的左右节点开始递归,相等就分别递归左->右(左孩子节点和右孩子节点比较),右->左(右孩子节点和左孩子节点比较)

rec(node.left,root.right);
rec(node.right,root.left);

root和node就是根节点的左右子树中每次递归往下的对应的对称元素的节点,一开始root和node都为根节点,相等往下递归

两个递归结果必须都为true结果才为true,采用与操作

 return rec(node.left,root.right)&&rec(node.right,root.left);

代码

  • 方法一
public class Solution {
    boolean isSymmetrical(TreeNode pRoot){
        TreeNode head = copyTree(pRoot);//pRoot作为镜像,head作为原二叉树
        mirroTree(pRoot);
        return rec(head,pRoot);
    }
    //递归判断两个二叉树是否相等
    public boolean rec(TreeNode head,TreeNode pRoot){
        if(head==null&&pRoot==null) return true;
        else if(head!=null&&pRoot!=null&&head.val==pRoot.val){
            boolean left = rec(head.left,pRoot.left);
            boolean right = rec(head.right,pRoot.right);
            return left&&right;
        }else return false;
    }
    //获取镜像二叉树
    public void mirroTree (TreeNode node){
        if(node==null) return ;
        if(node.left==null&&node.right==null) return ;
        TreeNode left = node.left;
        node.left = node.right;
        node.right = left;
        mirroTree(node.left);
        mirroTree(node.right);
    }
    //复制二叉树的每个节点
    TreeNode copyTree (TreeNode root) {
        if (root == null) return null;
        TreeNode t = new TreeNode(root.val);
        t.left = copyTree(root.left);
        t.right = copyTree(root.right);
        return t;
    }
}
  • 方法二
public class Solution {
    boolean isSymmetrical(TreeNode root){
        TreeNode node = root;
        return rec(node,root);
    }
    public boolean rec(TreeNode node,TreeNode root){
        if(node==null&&root==null) return true;
        if(node==null||root==null||node.val!=root.val) return false;
        return rec(node.left,root.right)&&rec(node.right,root.left);
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/mirro-btree.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!