101. 对称二叉树

101. 对称二叉树

题目:

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例:

示例 1:

img

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

img

输入:root = [1,2,2,null,3,null,3]
输出:false

提示:

  • 树中节点数目在范围 [1, 1000]
  • -100 <= Node.val <= 100

**进阶:**你可以运用递归和迭代两种方法解决这个问题吗?

解题:

方法一:递归

二叉树对称,说明它们关于根节点镜像,左子树=右子树,反之亦然。因此可以用两个指针,同时向根节点的左右子树两个方向遍历。

p指针左移,则q指针右移,每次移动检查当前指针所指向的节点的值是否相等,反之亦然。

/**
 * Definition for a binary tree node.
 * 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 check(TreeNode *p, TreeNode *q) {
        // 如果两个节点都为空,也是对称的
        if(!p && !q) return true;
        // 如果其中一个节点不为空,不对称
        if(!p || !q) return false;
        // 节点值不相等,不对称
        // 递归检查左子树的左子树与右子树的右子树,以及左子树的右子树与右子树的左子树
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

通俗易懂版本

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        // 如果两个节点都为空,也是对称的
        if(p == nullptr && q == nullptr) {
            return true;
        }
        // 如果其中一个节点不为空,不对称
        if(p == nullptr || q == nullptr) {
            return false;
        }
        // 节点值不相等,不对称
        if(p->val != q->val) {
            return false;
        }
        // 递归检查左子树的左子树与右子树的右子树,以及左子树的右子树与右子树的左子树
        return check(p->left, q->right) && check(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

复杂度分析

假设树上一共 n 个节点。

  • 时间复杂度:这里遍历了这棵树,渐进时间复杂度为 O(n)。
  • 空间复杂度:这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过 n,故渐进空间复杂度为 O(n)。

方法二:迭代

基本思路是使用队列,将每一层的节点按照对称的顺序加入队列,然后依次比较队列中的节点是否对称。每次从队列中取出两个节点进行比较,并按照对称的顺序将它们的子节点加入队列。**要注意的是根节点要加入队列两次。**当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。

class Solution {
public:
  	bool check(TreeNode *u, TreeNode *v) {
        queue<TreeNode*> q;
        q.push(u); q.push(v);
        while(!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if(!u && !v) continue;
            if((!u || !v) || u->val != v->val)) return false;
            q.push(u->left);
            q.push(v->right);
            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }
    bool isSymmetric(TreeNode *root) {
        return check(root, root);
    }
};

复杂度分析

  • 时间复杂度:O(n),同「方法一」。

  • 空间复杂度:这里需要用一个队列来维护节点,每个节点最多进队一次,出队一次,队列中最多不会超过 n 个点,故渐进空间复杂度为 O(n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/176639.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【云原生-Kurbernetes篇】 玩转K8S不得不会的HELM

Helm 一、Helm1.1 使用背景1.2 Helm简介1.3 Helm的几个概念1.4 helm2 和 helm3 的区别1.5 chart包的关键组成 二、Helm相关命令2.1 应用管理操作2.2 Helm repository仓库管理命令2.2 Helm chart包管理命令2.3 Helm release(实例) 管理命令2.4 Helm私有仓库管理命令 三、部署He…

react大文件上传

目录 大文件上传优点&#xff1a; 大文件上传缺点: 大文件上传原理&#xff1a; 为什么要用md5 实现流程&#xff1a; 部分代码1&#xff1a; 部分代码2&#xff1a;​ 大文件上传优点&#xff1a; 文件太大分片上传能加快上传速度,提高用户体验能断点续传 如果上次上传失败…

C++:继承

一、继承的概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保 持原有类特性的基础上进行扩展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。继承呈现了面向对象 程序设计的层次结构&#xff0c…

网络异常检测

随着社交网络、视频流、点对点技术、云计算和 SaaS 的出现&#xff0c;可以肯定地说&#xff0c;现代企业的好坏取决于他们的网络&#xff0c;尤其是在它们提供的带宽和安全性方面。无论是银行保护其数据免遭盗窃&#xff0c;还是商业组织保护其网络免受安全威胁和攻击&#xf…

Linux 中 .tar 和 tar.gz 的区别

1、前言 有时候你会发现&#xff0c;即便是有些拥有 3 年左右工作经验的运维或开发工程师对 .tar 和 .tar.gz 的区别并不是很清楚。.tar 和 .tar.gz 是在 Linux 系统中用于打包和压缩文件的两种常见格式。它们之间的主要区别在于压缩算法和文件扩展名。 2、区别 .tar .tar 是…

python练习题(markdown中的60道题)

1.Demo01 摄氏温度转化为华氏温度 celsius float(input(输入摄氏温度&#xff1a;)) fahrenheit (9/5)*celsius 32 print(%0.1f 摄氏温度转为华氏温度为 %0.1f % (celsius, fahrenheit))结果&#xff1a; 2.Demo02 计算圆柱体的体积 h, r map(float, input().split())# …

581. 最短无序连续子数组

581. 最短无序连续子数组 题目&#xff1a; 给你一个整数数组 nums &#xff0c;你需要找出一个 连续子数组 &#xff0c;如果对这个子数组进行升序排序&#xff0c;那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组&#xff0c;并输出它的长度。 示例&…

【Android】声浪 UI 效果并附上详细代码

声浪效果是基于第三方实现的。 https://github.com/xfans/VoiceWaveView 将三方的 Kotlin 代码转 java 使用&#xff08;按照他的readme 进行依赖&#xff0c;好像少了点东西&#xff0c;至少本项目跑不起来&#xff09; 声浪效果在android 8 以上都是比较好的&#xff0c;不会…

【JavaEE】操作系统与进程

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文录入于《JavaEE》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&…

Oracle的控制文件多路复用,控制文件备份,控制文件手工恢复

一.配置控制文件多路复用 1.查询Oracle的控制文件所在位置 SQL> select name from v$controlfile;NAME -------------------------------------------------------------------------------- /u01/app/oracle/oradata/orcl/control01.ctl /u01/app/oracle/fast_recovery_a…

规划类3d全景线上云展馆帮助企业轻松拓展海外市场

科技3D线上云展馆作为一种基于VR虚拟现实和互联网技术的新一代展览平台。可以在线上虚拟空间中模拟真实的展馆&#xff0c;让观众无需亲自到场&#xff0c;即可获得沉浸式的参观体验。通过这个展馆&#xff0c;您可以充分、全面、立体展示您的产品、服务以及各种创意作品&#…

实用篇 | T-SNE可视化工具详情及代码示例

本文主要是为了快速的了解t-sne和如何快速使用&#xff01; 简要了解TSNE TSNE&#xff0c;降维方法之一。降维在机器学习中非常重要。这是因为如果使用高维数据创建模型&#xff0c;则很容易欠拟合。换句话说&#xff0c;有太多无用的数据需要学习。可以通过从各种数据中仅…

Golang版本处理Skywalking Trace上报数据

Tips: 中间记录了解决问题的过程&#xff0c;如不感兴趣可直接跳至结尾 首先去es里查询skywalking trace的元数据 可以拿到一串base64加密后的data_binary(直接解密不能用&#xff0c;会有乱码&#xff0c;可参考https://github.com/apache/skywalking/issues/7423) 对data_b…

第四代智能井盖传感器:智能井盖位移怎么进行监测

井盖是城市基础设施的一个重要组成部分&#xff0c;若井盖出现移位等现象&#xff0c;可能会对路过的车辆和行人造成潜在危险。特别是那些含有甲烷气体的井盖&#xff0c;一旦气体超过阈值且被意外踩踏&#xff0c;可能会导致气体的释放&#xff0c;这便会引发一系列安全事故&a…

Linux wait函数用法

wait 函数是用于等待子进程结束并获取子进程的终止状态的系统调用。它在父进程中使用&#xff0c;用于等待其子进程终止并获得子进程的退出状态。 函数原型&#xff1a; pid_t wait(int *status);status 是一个指向整型的指针&#xff0c;用于存储子进程终止时的退出状态&…

clang+llvm多进程gdb调试

clangllvm多进程gdb调试 前言1. 命令行gdb2. 父进程调试3. 子进程调试4. 返回父进程 前言 在学习新增llvm的优化pass时&#xff0c;需要跟踪clang及llvm的调用栈。然而llvm通过posix_spawn()创建了新进程&#xff0c;这使得gdb调试必须有一定的技巧了。 1. 命令行gdb 以下命…

小红书干货类笔记怎么写?建议收藏

小红书干货类笔记是指在小红书这个社交平台上&#xff0c;用户分享的各种实用、有价值的生活技巧、经验、心得等内容的笔记。这类笔记通常具有以下特点&#xff1a;内容详实、实用性强、独特见解、图文并茂。 比如&#xff1a;某个妆要怎么化、某种技能该怎么学、某个城市该怎…

详细梳理山姆·奥特曼离职闹剧 仍试图重返OpenAI

大家好,我是极智视界,欢迎关注我的公众号,获取我的更多前沿科技分享 邀您加入我的知识星球「极智视界」,星球内有超多好玩的项目实战源码和资源下载,链接:https://t.zsxq.com/0aiNxERDq OpenAI 与微软围绕 Sam Altman 的离职风波,这场肥皂剧似乎还没到终结的样子。目前 …

跨越行业边界,CodeMeter护航AI领域安全与合规

在人工智能&#xff08;AI&#xff09;技术如ChatGPT的推动下&#xff0c;工业视觉、医疗诊断和智能驾驶等领域正在经历重大变革。这些技术不仅扩大了应用范围&#xff0c;也带来了数据安全、软件授权保护和合规性等新挑战。 AI工业视觉正在推动制造和自动化的快速发展&#x…

YOLOv5结合华为诺亚VanillaNet Block模块

🗝️YOLOv5实战宝典--星级指南:从入门到精通,您不可错过的技巧   -- 聚焦于YOLO的 最新版本, 对颈部网络改进、添加局部注意力、增加检测头部,实测涨点 💡 深入浅出YOLOv5:我的专业笔记与技术总结   -- YOLOv5轻松上手, 适用技术小白,文章代码齐全,仅需 …