【leetcode刷题】23.对称二叉树——Java版

前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

还剩一小时，加油！

Question

101. 对称二叉树

难度：简单

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

  1
 / \
2   2
/ \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1
 / \
2   2
 \   \
 3    3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

Solution

先观察一下，对称二叉树有什么特性呢？

先序遍历和后序遍历一样对吧，但是这么做时间复杂度也太高了

所以还是递归

镜像对称，就是左右两边相等，也就是左子树和右子树是相当的。也就是说要递归的比较左子树和右子树。

递归结束条件：

• 都为空指针则返回 true
• 只有一个为空则返回 false

递归过程：

• 判断两个指针当前节点值是否相等
• 判断 A 的右子树与 B 的左子树是否对称
• 判断 A 的左子树与 B 的右子树是否对称

Code

所有leetcode代码已同步至github

欢迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
    }
}

Result

复杂度分析

• 时间复杂度：O(N)

🌈寻宝

⭐今天是坚持刷题更文的第23/100天

⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力

⭐更多算法题欢迎关注专栏《leetcode》

为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等

怎么领取请大家自己找，寻宝游戏现在开始。

找不到可以评论留言，一条就会注意到你。

如果还不行，请私信我。