对称二叉树详解
【摘要】 CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
欢迎小伙伴们点赞👍、收藏⭐、留言💬
🎈 作者:
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 关注专栏:
(优质好文持续更新中……)🚀🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
一、题目描述
给定一个二叉树,检查它是否是镜像对称的。
二、测试样例
例如,二叉树 [1,2,2,3,4,4,3]
是对称的,如下所示:
但是下面这个 [1,2,2,null,3,null,3]
则不是镜像对称的,如下所示:
三、算法思路
首先,需要理解什么是对称二叉树,在上述例子中可以看到,对称二叉树其左右子树都是对称二叉树。那么,我们可以使用递归的方法来计算二叉树是否是对称二叉树,即:不断递归判断其左右子树是否是对称二叉树。
四、代码实现
递归算法实现如下所示:
五、复杂度分析
5.1 时间复杂度
时间复杂度为:O(n),在上述算法中,访问二叉树中的每个节点两次,故时间复杂度为O(n)。
5.2 空间复杂度
空间复杂度:O(n),在上述算法中,空间复杂度在于递归访问的栈的深度,深度最大为 n,故空间复杂度为O(n)。
六、总结
需要对二叉树有一定理解,理解对称二叉树,同时要掌握递归访问二叉树。
CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
欢迎小伙伴们点赞👍、收藏⭐、留言💬
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)