镜像二叉树(LeetCode101. 对称二叉树)

题目

解析

1. 层次遍历的方式。按层次遍历二叉树，观察当前层次的节点是否成折叠对称的关系，如果不是直接判断不是镜像二叉树。否则继续遍历下一层次 。
2. 递归实现。从根节点起，比较起左右孩子是否成镜像关系，如果不是，直接判断不是镜像二叉树，否则递归的方式去比较左孩子的左孩子与右孩子的右孩子，左孩子的右孩子与右孩子的左孩子的镜像关系，直到叶子节点。

代码

使用递归实现的方式，代码简单易懂。

public boolean isSymmetric(TreeNode root) {
    if(null == root){
        return true;
    }
    return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode r1, TreeNode r2){
    //判断传入的两个节点是否属于镜像关系
    //如果两个节点都为null，结束递归调用
    if(r1 == null && r2 == null){
        return true;
    }
    //如果不符合镜像关系直接返回结果
    if(r1 != null  && r2 == null){
        return false;
    }
    if(r2 != null && r1 == null){
        return false;
    }
    if(r1.val != r2.val){
        return false;
    }
    //递归左孩子的左孩子与右孩子的右孩子
    boolean m1 = isMirror(r1.left, r2.right);
    //递归左孩子的右孩子与右孩子的左孩子
    boolean m2 = isMirror(r1.right, r2.left);
    return m1 && m2;
}