【力扣题解】P101-对称二叉树-Java题解

2023-12-27 00:04

本文主要是介绍【力扣题解】P101-对称二叉树-Java题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

花无缺

👨‍💻博客主页:@花无缺
欢迎 点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏 【力扣题解】


文章目录

  • 【力扣题解】P101-对称二叉树-Java题解
    • 🌏题目描述
    • 💡题解
    • 🌏总结


【力扣题解】P101-对称二叉树-Java题解

P101.对称二叉树

🌏题目描述

给你一个二叉树的根节点 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

💡题解

递归法

public boolean isSymmetric(TreeNode root) {return recur(root.left, root.right);
}
// 深度优先搜索, 递归法
// 递归终止条件:
// 1.两个节点都为空
// 2.仅有一个节点为空
// 3.两个节点的值不相等
public boolean recur(TreeNode L, TreeNode R) {// 两个节点都为空if (L == null && R == null) {return true;}// 仅有一个节点为空if (L == null || R == null) {return false;}// 两个节点的值不相等if (L.val != R.val) {return false;}// 如果当前两个对应的节点是对称的, 那么递归判断这两个节点对应的左右孩子节点是否对称return recur(L.left, R.right) && recur(L.right, R.left);
}

算法数据复杂度:O(n),需要遍历树的所有节点,节点数为 n。

迭代法

public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();// 首先将根节点的左右孩子入队queue.offer(root.left);queue.offer(root.right);while (!queue.isEmpty()) {// 将队头两个节点出队TreeNode l = queue.poll();TreeNode r = queue.poll();// 如果两个节点都为空, 判断下一对节点if (l == null && r == null) {continue;}// 如果仅有一个节点为空, 说明不是对称的if (l == null || r == null) {return false;}// 如果两节点值不相等也不对称if (l.val != r.val) {return false;}// 将左节点的左孩子和右节点的右孩子入队// 之后进行判断queue.offer(l.left);queue.offer(r.right);// 将左节点的右孩子和右节点的左孩子入队// 之后进行判断queue.offer(l.right);queue.offer(r.left);}return true;
}

算法数据复杂度:O(n),需要遍历树的所有节点,节点数为 n。

🌏总结

这个题其实是对树的两个子树进行遍历,首先我们要明确一棵二叉树要满足哪些条件它会是对称二叉树:

  • 左右子树为空
  • 左孩子节点等于右孩子节点
  • 左子树的左孩子节点等于右子树的右孩子节点,左子树的右孩子节点等于右子树的左孩子节点

根据以上三个条件我们就可以写出对应的递归算法。

同样,迭代法也是如此,对应迭代法,我们采用一个队列,首先将树的左右子树节点进队,然后对这两个节点进行以上三点判断,再将他们的左右子树对应的节点入队,如此循环,便可以判断树是否是对称的。

作者:花无缺(huawuque404.com)


🌸欢迎关注我的博客:花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏:【力扣题解】
🥇往期精彩好文:
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏⭐ 留言📝 关注✅
是我持续创作,输出优质内容的最大动力!
谢谢!

这篇关于【力扣题解】P101-对称二叉树-Java题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/541255

相关文章

SpringCloud中的@FeignClient注解使用详解

《SpringCloud中的@FeignClient注解使用详解》在SpringCloud中使用Feign进行服务间的调用时,通常会使用@FeignClient注解来标记Feign客户端接口,这篇文章... 在Spring Cloud中使用Feign进行服务间的调用时,通常会使用@FeignClient注解

Java Spring 中的监听器Listener详解与实战教程

《JavaSpring中的监听器Listener详解与实战教程》Spring提供了多种监听器机制,可以用于监听应用生命周期、会话生命周期和请求处理过程中的事件,:本文主要介绍JavaSprin... 目录一、监听器的作用1.1 应用生命周期管理1.2 会话管理1.3 请求处理监控二、创建监听器2.1 Ser

JVisualVM之Java性能监控与调优利器详解

《JVisualVM之Java性能监控与调优利器详解》本文将详细介绍JVisualVM的使用方法,并结合实际案例展示如何利用它进行性能调优,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录1. JVisualVM简介2. JVisualVM的安装与启动2.1 启动JVisualVM2

Java如何从Redis中批量读取数据

《Java如何从Redis中批量读取数据》:本文主要介绍Java如何从Redis中批量读取数据的情况,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一.背景概述二.分析与实现三.发现问题与屡次改进3.1.QPS过高而且波动很大3.2.程序中断,抛异常3.3.内存消

SpringBoot使用ffmpeg实现视频压缩

《SpringBoot使用ffmpeg实现视频压缩》FFmpeg是一个开源的跨平台多媒体处理工具集,用于录制,转换,编辑和流式传输音频和视频,本文将使用ffmpeg实现视频压缩功能,有需要的可以参考... 目录核心功能1.格式转换2.编解码3.音视频处理4.流媒体支持5.滤镜(Filter)安装配置linu

在Spring Boot中实现HTTPS加密通信及常见问题排查

《在SpringBoot中实现HTTPS加密通信及常见问题排查》HTTPS是HTTP的安全版本,通过SSL/TLS协议为通讯提供加密、身份验证和数据完整性保护,下面通过本文给大家介绍在SpringB... 目录一、HTTPS核心原理1.加密流程概述2.加密技术组合二、证书体系详解1、证书类型对比2. 证书获

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

Java实现本地缓存的常用方案介绍

《Java实现本地缓存的常用方案介绍》本地缓存的代表技术主要有HashMap,GuavaCache,Caffeine和Encahche,这篇文章主要来和大家聊聊java利用这些技术分别实现本地缓存的方... 目录本地缓存实现方式HashMapConcurrentHashMapGuava CacheCaffe

SpringBoot整合Sa-Token实现RBAC权限模型的过程解析

《SpringBoot整合Sa-Token实现RBAC权限模型的过程解析》:本文主要介绍SpringBoot整合Sa-Token实现RBAC权限模型的过程解析,本文给大家介绍的非常详细,对大家的学... 目录前言一、基础概念1.1 RBAC模型核心概念1.2 Sa-Token核心功能1.3 环境准备二、表结

eclipse如何运行springboot项目

《eclipse如何运行springboot项目》:本文主要介绍eclipse如何运行springboot项目问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目js录当在eclipse启动spring boot项目时出现问题解决办法1.通过cmd命令行2.在ecl