【LeetCode】101. 对称二叉树

101. 对称二叉树

难度:简单

题目

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

示例 1:

在这里插入图片描述

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

示例 2:

在这里插入图片描述

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

提示:

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

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

个人题解

方法一:递归-深度优先遍历

写了 100 题后再写这题,信手捏来。先判断当前节点是否为空。再判断当前节点的左节点和右节点是否相等。再看左左节点与右右节点,再比较左右节点与右左节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return process(root.left, root.right);
    }
    public boolean process(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null ^ right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        if (!process(left.left, right.right)) {
            return false;
        }
        return process(left.right, right.left);
    }
}

官方题解

方法一:递归

如果一个树的左子树与右子树镜像对称,那么这个树是对称的。因此,该问题可以转化为:两个树在什么情况下互为镜像?

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

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

我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,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);
    }
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法二:迭代

「方法一」中我们用递归的方法实现了对称性的判断,那么如何用迭代的方法实现呢?首先我们引入一个队列,这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值(队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像),然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。

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

    public boolean check(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

作者:力扣官方题解
链接:https://leetcode.cn/problems/symmetric-tree/solutions/268109/dui-cheng-er-cha-shu-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

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

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

相关文章

Java高级技术(注解)

一&#xff0c;注解 二&#xff0c;案例 三&#xff0c;注解原理 四&#xff0c;元注解 五&#xff0c;案例 六&#xff0c;解析注解 七&#xff0c;案例

本地部署GPT的实战方案

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…

C++面向对象复习笔记暨备忘录

C指针 指针作为形参 交换两个实际参数的值 #include <iostream> #include<cassert> using namespace std;int swap(int *x, int* y) {int a;a *x;*x *y;*y a;return 0; } int main() {int a 1;int b 2;swap(&a, &b);cout << a << &quo…

多模块项目打包部署

目录结构 这些模块间相互依赖&#xff0c;打包的时候打父模块&#xff0c;就是带root的这个 先clean&#xff0c;再package&#xff0c;就跟一般的项目一样了。 有可能遇到报错Failed to execute goal org.apache.maven.plugins:maven-surefire-plugin:2.22.2:test&#xff…

springboot基础配置及maven运行

目录 1、spring快速开始&#xff1a; 2、通过idea工具打开导入包 3、maven打包 1、springboot快速开始&#xff1a; 环境依赖&#xff1a;jdk17 Spring | Quickstart spring初始化包下载&#xff1a; 点击generate&#xff0c;下载包 2、通过idea工具打开导入包 我之前写了…

【云备份】热点管理模块

文章目录 整体思路概括热点管理实现构造函数Hotjudge ——热点判断RunModule ——运行模块 代码实现hot.hpp 整体思路概括 整体概括&#xff1a; 对服务器上备份的文件进行检测&#xff0c;那些文件长时间没有被访问&#xff0c;则认为是非热点文件 进行压缩存储&#xff0c;节…

华清远见嵌入式学习——C++——作业2

作业要求&#xff1a; 代码&#xff1a; #include <iostream>using namespace std;class Rect { private:int width;int height;public:void init(int w,int h);void set_w(int w);void set_h(int h);void show(); };void Rect::init(int w,int h) {width w;height h;…

BUUCTF sqltest 1

BUUCTF:https://buuoj.cn/challenges 题目描述&#xff1a; 网站遭受到攻击了&#xff0c;还好我们获取到了全部网络流量。 链接: https://pan.baidu.com/s/1AdQXVGKb6rkzqMLkSnGGBQ 提取码: 34uu 注意&#xff1a;得到的 flag 请包上 flag{} 提交 密文&#xff1a; 下载附件…

GDPU 数据结构 天码行空12

文章目录 数据结构实验十二 图的遍历及应用一、【实验目的】二、【实验内容】三、实验源代码&#x1f37b; CPP&#x1f37b; C 数据结构实验十二 图的遍历及应用 一、【实验目的】 1、 理解图的存储结构与基本操作&#xff1b; 2、熟悉图的深度度优先遍历和广度优先遍历算法…

RabbitMQ的Web管理页面

访问页面 http://IP:15672/账号密码默认都是&#xff1a;guest 主页概览 Overview 显示当前RabbitMQ Broker的运行信息、连接信息、集群信息以及配置信息等。 连接 Connections 无论生产者还是消费者&#xff0c;都需要与RabbitMQ建立连接后才可以完成消息的生产和消费&#…

PHP:js中怎么使用PHP变量,php变量为数组时的处理

方法一&#xff1a;使用内嵌 PHP 脚本标记 1、简单的拼接 使用内嵌的 PHP 脚本标记 <?php ?> 将 PHP 变量 $phpVariable 的值嵌入到 JavaScript 代码中。 <?php $phpVariable "Hello, World!"; ?><script> // 将 PHP 变量的值传递给 JavaS…

mac安装homebrew/brew遇到443

文章目录 问题描述解决方法方法一方法二 参考文献 问题描述 brew 全称Homebrew 是Mac OSX上的软件包管理工具 想在mac终端安装&#xff0c;运行网上提供的指令 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)&quo…

【Springboot系列】SpringBoot整合Jpa

文章目录 前言&#xff1a;什么是JPA&#xff1f;JPA优缺点优点1.简化开发&#xff1a;2.高度抽象&#xff1a;3.跨数据库支持&#xff1a;4.自动化的事务管理&#xff1a; 缺点1.学习成本较高&#xff1a;2.性能问题&#xff1a;3.灵活性受限&#xff1a; 示例版本依赖代码Use…

Ubuntu安装nfs服务步骤

Ubuntu安装nfs服务步骤 一、NFS&#xff1f; NFS&#xff1a;网络文件系统&#xff08;Network File system File&#xff09;缩写&#xff0c;可通过网络让不同的机器&#xff0c;不同操作系统之间可以彼此共享文件和目录。 二、安装 1.安装nfs服务器命令&#xff1a;sudo…

原神:夏洛蒂是否值得培养?全队瞬抬治疗量不输五星,但缺点也很明显

作为四星冰系治疗角色&#xff0c;夏洛蒂的实战表现可以说相当让人惊喜。不仅有相当有意思的普攻动作以及技能特效&#xff0c;而且她还有治疗和挂冰等功能性。下面就来详细聊聊夏洛蒂是否值得培养。 【治疗量让人惊喜&#xff0c;但也有缺点】 说实话&#xff0c;在使用夏洛蒂…

智能手表上的音频(四):语音通话

上篇讲了智能手表上音频文件播放。本篇开始讲语音通话。同音频播放一样有两种case&#xff1a;内置codec和BT。先看这两种case下audio data path&#xff0c;分别如下图&#xff1a; 内置codec下的语音通话audio data path 蓝牙下的语音通话audio data path 从上面两张图可以看…

【Lustre相关】应用部署-03-Lustre集群部署实践(软raid方案)

文章目录 一、前言1、硬件配置2、组网拓扑3、总体方案 二、软件安装三、集群部署1、配置多路径2、配置高可用集群3、配置zpool4、部署lustre5、配置Lustre角色高可用6、配置Lustre状态监控6.1、Lustre网络状态监控6.2、Lustre集群状态监控6.3、配置优化6.3.1、设置故障恢复不回…

springboot整合easy-es实现数据的增删改查

背景 目前公司的一个老项目&#xff0c;查询贼慢&#xff0c;需要想办法提升一下速度&#xff0c;于是就想到了ES&#xff0c;现在尝试一下将ES整合到项目中来提升检索效率。 ES是基于倒排索引实现的&#xff0c;倒排索引中一个表相当于一个索引&#xff0c;表中的每条记录都…

飞翔的小鸟——Java

一、创建文件、包、类、插入图片文件 二、app包 1、Gameapp类&#xff08;运行游戏&#xff09; package app;import main.GameFrame;public class Gameapp {public static void main(String[] args) {//游戏的入口new GameFrame();} } 三、main包 1、Barrier&#xff08…

Django大回顾 -3 之响应对象、cbv和fbv、关于类中self是谁的问题、上传文件、模版

【1】isinstance方法 判断一个对象是否是一个已知的类型。 isinstance语法&#xff1a; isinstance(object&#xff0c;classinfo) object --------- 实例化对象 cassinfo ------- 可以是字节或间接类名、基本类型&#xff0c;或者由他们组成的元组 相同返回True&#xff0c;不…