​LeetCode刷题实战101:对称二叉树

程序IT圈

共 1124字,需浏览 3分钟

 ·

2020-11-20 20:35

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 对称二叉树,我们先来看题面:

https://leetcode-cn.com/problems/symmetric-tree/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

题意


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

样例

解题


方法:递归

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。

因此,该问题可以转化为:两个树在什么情况下互为镜像?

如果同时满足下面的条件,两个树互为镜像:

它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,p 指针和 q 指针一开始都指向这棵树的根,随后 p 右移时,q 左移,p 左移时,q 右移。每次检查当前 p 和 q 节点的值是否相等,如果相等再判断左右子树是否对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}


对于这道题,你还有什么其他解法吗?
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:

LeetCode1-100题汇总,希望对你有点帮助!

浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报