当前位置: 首页 > news >正文

LeetCode-101. 对称二叉树

目录

    • 题目分析
    • 递归法

题目来源
101. 对称二叉树

题目分析

首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点!

对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。

那么如何比较呢?
比较的是两个子树的里侧和外侧的元素是否相等。如图所示:
在这里插入图片描述
那么遍历的顺序应该是什么样的呢?

本题遍历只能是“后序遍历”,因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点,所以准确的来说是左树的遍历顺序是左右中,右树的遍历顺序是右左中。

递归法

递归三部曲

  • 1.确定递归函数的参数和返回值
    因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。
boolean compare(TreeNode left,TreeNode right)
  • 2.确定终止条件
    要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。
    节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)
    • 左节点为空,右节点不为空,不对称,return false
    • 左不为空,右为空,不对称 return false
    • 左右都为空,对称,返回true
    • 左右都不为空,比较节点数值,不相同就return false
        // 首先排除空节点的情况if (left == null && right != null){return false;} else if (left != null && right == null) {return false;}else if (left == null && right == null) {return true;// 排除了空节点,再排除数值不相同的情况}else if (left.val != right.val){return false;}
  • 3.确定单层递归的逻辑
    此时才进入单层递归的逻辑,单层递归的逻辑就是处理 左右节点都不为空,且数值相同的情况。
    • 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
    • 比较内测是否对称,传入左节点的右孩子,右节点的左孩子。
    • 如果左右都对称就返回true ,有一侧不对称就返回false 。
        // 此时就是:左右节点都不为空,且数值相同的情况// 此时才做递归,做下一层的判断boolean outside = compare(left.left,right.right);   // 左子树:左、 右子树:右boolean inside = compare(left.right,right.left);    // 左子树:右、 右子树:左// 左子树:中、 右子树:中 (逻辑处理)boolean result = outside && inside;

代码实现

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return compare(root.left,root.right);}public static boolean compare(TreeNode left,TreeNode right){// 首先排除空节点的情况if (left == null && right != null){return false;} else if (left != null && right == null) {return false;}else if (left == null && right == null) {return true;// 排除了空节点,再排除数值不相同的情况}else if (left.val != right.val){return false;}// 此时就是:左右节点都不为空,且数值相同的情况// 此时才做递归,做下一层的判断boolean outside = compare(left.left,right.right);   // 左子树:左、 右子树:右boolean inside = compare(left.right,right.left);    // 左子树:右、 右子树:左// 左子树:中、 右子树:中 (逻辑处理)boolean result = outside && inside;return result;}
}

在这里插入图片描述

相关文章:

LeetCode-101. 对称二叉树

目录题目分析递归法题目来源 101. 对称二叉树 题目分析 首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一…...

使用intlinprog求解指派问题MATLAB代码分享

% 输入指派矩阵C [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];f C(:); %生成一个列向量,作为目标函数系数,matlab默认以列排序[m,n] size(C);Aeq zeros(2*n,n*n); %2*n个等式约束,n*n个变量for i 1:n %这里先生成的是后5个…...

Spark On YARN时指定Python版本

坑很多&#xff0c;直接上兼容性最佳的命令&#xff0c;将python包上传到hdfs或者file:/home/xx/(此处无多余的/) # client 模式 $SPARK_HOME/spark-submit \ --master yarn \ --deploy-mode client \ --num-executors 2 \ --conf "spark.yarn.dist.archives<Python包…...

[数据库]库的增删改查

●&#x1f9d1;个人主页:你帅你先说. ●&#x1f4c3;欢迎点赞&#x1f44d;关注&#x1f4a1;收藏&#x1f496; ●&#x1f4d6;既选择了远方&#xff0c;便只顾风雨兼程。 ●&#x1f91f;欢迎大家有问题随时私信我&#xff01; ●&#x1f9d0;版权&#xff1a;本文由[你帅…...

Wine零知识学习1 —— 介绍

一、什么是Wine Wine是“Wine Is Not an Emulator” 的首字母缩写&#xff0c;是一个能够在多种POSIX-compliant操作系统&#xff08;诸如Linux、macOS及BSD等&#xff09;上运行 Windows 应用的兼容层。Wine不像虚拟机或者模拟器那样模仿内部的Windows逻辑&#xff0c;而是將…...

设计模式--建造者模式 builder

设计模式--建造者模式 builder&#xff09;建造者模式简介建造者模式--小例子&#xff08;电脑购买&#xff09;1.产品类2.抽象构建者3.实体构建类4.指导者类5.客户端测试类小结建造者模式简介 建造者模式有四个角色,概念划分如下&#xff1a; Product &#xff1a; 产品类&a…...

终于周末啦,继续来总结一下Python的一些知识点啦

目录 Python概念梳理 常见概念梳理 Python经典判断题 判断题 选择题 Python概念梳理 常见概念梳理 Python中&#xff0c;不仅仅变量的值是可以变化的&#xff0c;类型也是可以随时变化的 1、Python的变量必须初始化否则提示 is not defined 2、if、while中定义的变量在…...

CUDA By Example(八)——流

文章目录页锁定主机内存可分页内存函数页锁定内存函数CUDA流使用单个CUDA流使用多个CUDA流GPU的工作调度机制高效地使用多个CUDA流遇到的问题(未解决)页锁定主机内存 在之前的各个示例中&#xff0c;都是通过 cudaMalloc() 在GPU上分配内存&#xff0c;以及通过标准的C库函数 …...

02- pandas 数据库 (数据库)

pandas 数据库重点: pandas 的主要数据结构: Series (一维数据)与 DataFrame (二维数据)。 pd.DataFrame(data np.random.randint(0,151,size (5,3)), # 生成pandas数据 index [Danial,Brandon,softpo,Ella,Cindy], # 行索引 …...

less常用语法总结

CSS预处理器 CSS 预处理器是什么?一般来说,它们基于 CSS 扩展了一套属于自己的 DSL,来解决我们书写 CSS 时难以解决的问题: 语法不够强大,比如无法嵌套书写导致模块化开发中需要书写很多重复的选择器;没有变量和合理的样式复用机制,使得逻辑上相关的属性值必须以字面量…...

DHCP Relay中继实验

DHCP Relay实验拓扑图设备配置结果验证拓扑图 要求PC1按照地址池自动分配&#xff0c;而PC要求分配固定的地址&#xff0c;网段信息已经在图中进行标明。 设备配置 AR1&#xff1a; AR1作为DHCP Server基本配置跟DHCP Server没区别&#xff0c;不过要加一条静态路由&#xff…...

“1+1>2”!《我要投资》与天际汽车再度“双向奔赴”!

文|螳螂观察 作者| 图霖 胡海泉老师重磅回归、创始人现场真情告白……新一季的《我要投资》&#xff0c;不仅维持了往季在专业度上的高水准&#xff0c;也贡献了不少高话题度的“出圈”时刻。 在竞争激烈的的综艺节目竞技场&#xff0c;能举办数季的节目&#xff0c;往往都是…...

【分享】订阅金蝶KIS集简云连接器同步OA付款审批数据至金蝶KIS

方案简介 集简云基于钉钉连接平台完成与钉钉的深度融合&#xff0c;实现钉钉OA审批与数百款办公应用软件&#xff08;如金蝶KIS、用友等&#xff09;的数据互通&#xff0c;让钉钉的OA审批流程与企业内部应用软件的采购、付款、报销、收款、人事管理、售后工单、立项申请等环节…...

dubbo服务消费

dubbo在服务消费时调用的方法栈比较深&#xff0c;所以得一边看一边记&#xff0c;还是比较费力的。在dubbo服务发现中&#xff0c;我们看到通过ReferenceConfig#get()返回的是要调用接口的代理对象&#xff0c;因此通过接口的代理对象调用方法时是调用InvocationHandler(Invok…...

Python调用API接口,实现人脸识别

人生苦短&#xff0c;我用Python 在开始之前&#xff0c;先问问大家&#xff1a; 什么是百度Aip模块&#xff1f; 百度AI平台提供了很多的API接口供开发者快速的调用运用在项目中 本文写的是使用百度AI的**在线接口SDK模块&#xff08;baidu-aip&#xff09;**进行实现人脸识…...

2月10日刷题总结

编辑距离题目描述设 AA 和 BB 是两个字符串。我们要用最少的字符操作次数&#xff0c;将字符串 AA 转换为字符串 BB。这里所说的字符操作共有三种&#xff1a;删除一个字符&#xff1b;插入一个字符&#xff1b;将一个字符改为另一个字符。A, BA,B 均只包含小写字母。输入格式第…...

C++学习/温习:新型源码学编程(三)

写在前面(祝各位新春大吉&#xff01;兔年如意&#xff01;) 【本文持续更新中】面向初学者撰写专栏&#xff0c;个人原创的学习C/C笔记&#xff08;干货&#xff09;所作源代码输出内容为中文&#xff0c;便于理解如有错误之处请各位读者指正请读者评论回复、参与投票&#xf…...

阿里云ecs服务器搭建CTFd(ubuntu20)

1.更新apt包索引 sudo apt-get update更新源 1、使用快捷键【ctrlaltt】打开终端。 2、输入以下命令备份原有软件源文件。 cp /etc/apt/sources.list /etc/apt/sources.list.bak_yyyymmdd 3、再输入以下命令打开sources.list文件并添加新的软件源地址。 vim /etc/apt/sources.…...

视频号小店新订单如何实时同步企业微信

随着直播带货的火热&#xff0c;视频号小店也为商家提供商品信息服务、商品交易&#xff0c;支持商家在视频号运营电商&#xff0c;许多企业也将产品的零售路径渗透至视频号小店中了。如果我们希望在视频号小店接收到订单后&#xff0c;能尽快及时发货&#xff0c;给用户较好的…...

ag-Grid Enterprise

ag-Grid Enterprise Ag-Grid被描述为一种商业产品&#xff0c;已在EULA下分发&#xff0c;它非常先进&#xff0c;性能就像Row分组一样&#xff0c;还有范围选择、master和case、行的服务器端模型等等。 ag Grid Enterprise的巨大特点&#xff1a; 它具有以下功能和属性&#x…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...