leetcode刷题101 对称二叉树 Symmetric Tree(简单) Python Java

2024-01-27 00:08

本文主要是介绍leetcode刷题101 对称二叉树 Symmetric Tree(简单) Python Java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意:

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

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1/ \2   2/ \ / \
3  4 4  3

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

    1/ \2   2\   \3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

解法一:递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""if not root:                                 # 先判断根节点是否为空return Truereturn self.isMirror(root.left, root.right)  # 分成左子树和右子树判断def isMirror(self, p, q):                        # 判断两棵树是否是镜像树if not p and not q:                          # 根节点都为空,是return Trueif not p or not q:                           # 其中有一棵为空,不是return Falsel = self.isMirror(p.left, q.right)           # p的左子树和q的右子树是否相同r = self.isMirror(p.right, q.left)           # p的右子树和q的左子树是否相同return p.val == q.val and l and r            # 值相等,并且p的左=q的右,p的右=q的左

解法二:使用队列

class Solution:def isSymmetric(self, root):"""队列:param root::return:"""if not root:return Truenode_queue = [root.left, root.right]  # 在空队列中加入左子树和右子树while node_queue:left = node_queue.pop(0)          # 依次弹出两个元素right = node_queue.pop(0)if not right and not left:        # 如果均为空,继续下一个循环continueif not right or not left:         # 如果只有一个为空,返回Falsereturn Falseif left.val != right.val:         # 都非空,再判断值是否相等return Falsenode_queue.append(left.left)      # 将两个左右子树的左右子树逆序加入队列node_queue.append(right.right)node_queue.append(left.right)node_queue.append(right.left)#node_queue.extend([left.left, right.right, left.right, right.left])   或者用这一句话写return True

 

以下是Java版本:

最简单的思路就是先从左子树然后右子树遍历,记录遍历结果,然后再右子树左子树遍历,记录遍历结果,然后对比

两个遍历结果,看是否相等。

1.	public class Solution {  
2.	    public boolean isSymmetric(TreeNode root) {  
3.	        if(root == null)  
4.	            return true;  
5.	        StringBuilder builderOfLeft = new StringBuilder();  
6.	        StringBuilder builderOfRight = new StringBuilder();  
7.	        String traverseLeft = traverseLeft(root,builderOfLeft);  
8.	        String traverseRight = traverseRight(root,builderOfRight);  
9.	        if(traverseLeft.equals(traverseRight)){  
10.	            return true;  
11.	        }  
12.	        return false;  
13.	    }  
14.	    public static String traverseLeft(TreeNode root,StringBuilder builder){  
15.	        if(root == null){  
16.	            builder.append("null");  
17.	            return null;  
18.	        }  
19.	        builder.append(root.val+"");  
20.	        traverseLeft(root.left,builder);  
21.	        traverseLeft(root.right,builder);  
22.	        return builder.toString();  
23.	    }  
24.	    public static String traverseRight(TreeNode root,StringBuilder builder){  
25.	        if(root == null){  
26.	            builder.append("null");  
27.	            return null;  
28.	        }             
29.	        builder.append(root.val+"");  
30.	        traverseRight(root.right,builder);  
31.	        traverseRight(root.left,builder);   
32.	        return builder.toString();  
33.	    }  
34.	}  

用递归:

1.	public class Solution {  
2.	    public boolean isSymmetric(TreeNode root) {  
3.	        if (root == null) {  
4.	            return true;  
5.	        }  
6.	        return isSymmetric(root.left, root.right);  
7.	    }  
8.	      
9.	    public boolean isSymmetric(TreeNode left, TreeNode right) {  
10.	        if (left == null && right == null) {  
11.	            return true;  
12.	        }  
13.	          
14.	        if (left == null || right == null) {  
15.	            return false;  
16.	        }  
17.	          
18.	        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);  
19.	    }  
20.	}  

 

这篇关于leetcode刷题101 对称二叉树 Symmetric Tree(简单) Python Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2

Python中你不知道的gzip高级用法分享

《Python中你不知道的gzip高级用法分享》在当今大数据时代,数据存储和传输成本已成为每个开发者必须考虑的问题,Python内置的gzip模块提供了一种简单高效的解决方案,下面小编就来和大家详细讲... 目录前言:为什么数据压缩如此重要1. gzip 模块基础介绍2. 基本压缩与解压缩操作2.1 压缩文

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客

Spring事务传播机制最佳实践

《Spring事务传播机制最佳实践》Spring的事务传播机制为我们提供了优雅的解决方案,本文将带您深入理解这一机制,掌握不同场景下的最佳实践,感兴趣的朋友一起看看吧... 目录1. 什么是事务传播行为2. Spring支持的七种事务传播行为2.1 REQUIRED(默认)2.2 SUPPORTS2

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域(Local)2.2 闭包作用域(Enclos

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java进程异常故障定位及排查过程

《Java进程异常故障定位及排查过程》:本文主要介绍Java进程异常故障定位及排查过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、故障发现与初步判断1. 监控系统告警2. 日志初步分析二、核心排查工具与步骤1. 进程状态检查2. CPU 飙升问题3. 内存

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os