LeetCode 101. 对称二叉树 | Python

ByteLumina
• 阅读 2393

101. 对称二叉树


题目


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

例如,二叉树 [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

进阶:

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

解题思路


如何去判断二叉树是镜像对称?如下:

  • 根节点为 null,直接返回 True;
  • 当根节点不为 null 时,判断左右子树是否对称:

    • 判断 root.left 跟 root.right 节点值是否相同
    • 判断 root.left 的左子树是否与 root.right 的右子树对称
    • 判断 root.left 的右子树是否与 root.right 的左子树对称

按照题目中【进阶】部分所述,本篇幅就从递归和迭代两种思路来解决该问题。

思路:递归

根据上面判断二叉树是否对称的思路,先设定递归终止的条件:

  • 如果都为空指针的情况下,返回 True
  • 其中一个不为空的情况下,返回 False

递归具体的过程:

  • 先判断当前两个指针节点值是否相等
  • 判断 t1 的左子树与 t2 的右子树是否对称
  • 判断 t1 的右子树与 t1 的左子树是否对称

具体代码实现见【代码实现:递归】。

思路:迭代

还是按照开篇的思路判断二叉树的对称,这次使用迭代的方法实现。这里需要引入一个队列。

具体的做法:

  • 初始化的时候,将根节点入队两次。
  • 循环的时候,每次出队两次提取两个节点,比较它们的值(因为子树互为镜像,它们的值应该是相等的)
  • 再次入队时,将两个节点的左右子节点按照相反的顺序进行入队。(例如: t1 节点的左子节点跟 t2 节点的右子节点连续入队)
  • 循环结束的条件,当队列为空的时候,或者连续出队的两个节点不相等时。

具体实现的代码见【代码实现:迭代

代码实现


代码实现:递归
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:      
        return self.check(root, root)
    
    def check(self, t1, t2):
            if t1 == None and t2 == None:
                return True
            if t1 == None or t2 == None:
                return False
            
            return t1.val == t2.val and self.check(t1.left, t2.right) and self.check(t1.right, t2.left)
代码实现:迭代
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 构建,初始化队列
        # 将根节点入队两次
        queue = []
        queue.append(root)
        queue.append(root)

        # 循环开始
        while len(queue) != 0:
            # 先连续出队,提取两个节点进行比较
            t1 = queue.pop()
            t2 = queue.pop()

            if t1 == None and t2 == None:
                continue
            # 当两个节点不相等,直接返回 False
            if t1 == None or t2 == None or t1.val != t2.val:
                return False

            # 重新入队,将两个节点的左右子节点按照相反的顺序入队
            queue.append(t1.left)
            queue.append(t2.right)

            queue.append(t1.right)
            queue.append(t2.left)
        
        return True

实现结果


实现结果:递归

LeetCode 101. 对称二叉树 | Python

实现结果:迭代

LeetCode 101. 对称二叉树 | Python

总结


  • 根据题意,按照递归和迭代的思路解决该问题
  • 具体的判断是否为镜像对称的思路:

    • 这里判断 root 不为空的情况(根节点为空,直接返回 True);
    • 判断 root.left 和 root.right 节点值是否相同;
    • 判断 root.left 的左子树和 root.right 的右子树是否对称;
    • 判断 root.left 的右子树和 root.right 的左子树是否对称。
  • 递归实现具体的过程:

    • 终止条件:指针都会空时,返回 True;其中一个指针为空时,返回 False;
    • 判断两个指针的节点值是否相同;
    • 判断 t1 的左子树是否与 t2 的右子树对称
    • 判断 t1 的右子树是否与 t2 的左子树对称
  • 迭代实现的具体过程:

    • 这里需要引入一个队列,首先初始化队列,先将 root 入队两次;
    • 循环开始,先连续出队两次,提取两个节点,比较它们的值(两个相邻的值应该是相等的,因为左右子树互为镜像)
    • 将两个节点的左右子节点按照相反的顺序进行入队(例如 t1 的左节点与 t2 的右节点连续入队)
    • 循环结束的条件,当队列为空的时候,或者出队的两个节点不相等(也就是不对称)。

欢迎关注微信公众号《书所集录》
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
12个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
java实现非对称加密
对称加密:加密和解密的过程使用的是相同的密钥!这里写图片描述(https://oscimg.oschina.net/oscnet/42e81282a912d5abcf561e846c2b997914e.png)非对称加密与对称加密不同,非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的”公开密钥”(公钥
Jacquelyn38 Jacquelyn38
4年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
OpenSSL和Python实现RSA Key公钥加密私钥解密
基于非对称算法的RSAKey主要有两个用途,数字签名和验证(私钥签名,公钥验证),以及非对称加解密(公钥加密,私钥解密)。本文提供一个基于OpenSSL和Python进行非对称加解密的例子。1\.OpenSSL实现非对称加解密1.1生成私钥,并导出公钥生成2048bit的PEM格式的RSAKey:Key.pem$openssl
Stella981 Stella981
3年前
LeetCode(110):平衡二叉树
Easy!题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树_每个节点_的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树 3,9,20,null,null,15,73/\920/
Stella981 Stella981
3年前
LeetCode112
非商业,LeetCode链接附上:https://leetcodecn.com/problems/pathsum/进入正题。题目:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树,以及目标和
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
1年前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
美凌格栋栋酱 美凌格栋栋酱
5个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(