使用递归判断二叉树对称

题目

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
《使用递归判断二叉树对称》
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
《使用递归判断二叉树对称》
说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

解法

解题思路:
先判断根节点 a 的左节点 b 和右节点 c 想不想等,不相等则返回false,相等的话,递归判断 b 的左子树 d 和 c 的右子树 g 是否相等、b 的右子树 e 和 c 的左子树 f 是否相等,如果相等,继续递归。
《使用递归判断二叉树对称》

代码:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution { 
    public boolean isSymmetric(TreeNode root) { 
        return isMirror(root,root);
    }
    
    public boolean isMirror(TreeNode root1,TreeNode root2) { 
        
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if(root1.val != root2.val) return false;
        
        //如果是第一个根节点,直接比较左右子树,避免重复比较
        if(root1 == root2) return isMirror(root1.left,root1.right);
        
        return isMirror(root1.left,root2.right)&&
                isMirror(root1.right,root2.left); 
    }
}
    原文作者:星空是梦想
    原文地址: https://blog.csdn.net/Abel_Liujinquan/article/details/89686246
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞