对称二叉树详解

举报
Linux猿 发表于 2021/12/20 23:58:53 2021/12/20
【摘要】 CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊! 欢迎小伙伴们点赞👍、收藏⭐、留言💬 


🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏:LeetCode面试必备100题 (优质好文持续更新中……)🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


一、题目描述

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

二、测试样例

例如,二叉树 [1,2,2,3,4,4,3] 是对称的,如下所示:

 

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


三、算法思路

首先,需要理解什么是对称二叉树,在上述例子中可以看到,对称二叉树其左右子树都是对称二叉树。那么,我们可以使用递归的方法来计算二叉树是否是对称二叉树,即:不断递归判断其左右子树是否是对称二叉树。

四、代码实现

递归算法实现如下所示:

#include <iostream>
using namespace std;

struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode() : val(0), left(nullptr), right(nullptr) {}
   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
class Solution {
public:
    bool checkSymmetric(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2) return true;
        if(!root1 || !root2) return false;
        if(root1->val != root2->val) return false;
        return checkSymmetric(root1->left, root2->right) && checkSymmetric(root1->right, root2->left);
    }
    bool isSymmetric(TreeNode* root) {
        return checkSymmetric(root, root);
    }
};

int main() {

}

五、复杂度分析

5.1 时间复杂度

时间复杂度为:O(n),在上述算法中,访问二叉树中的每个节点两次,故时间复杂度为O(n)。

5.2 空间复杂度

空间复杂度:O(n),在上述算法中,空间复杂度在于递归访问的栈的深度,深度最大为 n,故空间复杂度为O(n)。

六、总结

需要对二叉树有一定理解,理解对称二叉树,同时要掌握递归访问二叉树。


CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

欢迎小伙伴们点赞👍、收藏⭐、留言💬 


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。