Python对称的二叉树多种思路实现方法

对称二叉树的含义非常容易理解，左右子树关于根节点对称，具体来讲，对于一颗对称二叉树的每一颗子树，以穿过根节点的直线为对称轴，左边子树的左节点=右边子树的右节点，左边子树的右节点=左边子树的左节点。所以对称二叉树的定义是针对一棵树，而判断的操作是针对节点，这时可以采取由上到下的顺序，从根节点依次向下判断，只需要重复调用函数，不需要回溯。

题目：对称的二叉树题：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的

解题思路一：先遍历右子节点再遍历左子节点。注意，我们必须把遍历二叉树时遇到的空指针考虑进来。

class Solution:
  def isSymmetrical(self, pRoot):
    # write code here
    return self.isSymmetricalCore(pRoot,pRoot)

  def isSymmetricalCore(self,pRoot1,pRoot2):
    if not pRoot1 and not pRoot2:
      return True
    if not pRoot1 or not pRoot2:
      return False
    if pRoot1.val != pRoot2.val:
      return False
    return self.isSymmetricalCore(pRoot1.left,pRoot2.right) and self.isSymmetricalCore(pRoot1.right,pRoot2.left)

解题思路二：迭代

def isSymmetric(self, root: 'TreeNode') -> 'bool':
  stack = root and [(root.left, root.right)]
  while stack:
    p1, p2 = stack.pop()
    if not p1 and not p2: continue
    if not p1 or not p2: return False
    if p1.val != p2.val: return False
    stack.append((p1.left, p2.right))
    stack.append((p1.right, p2.left))
  return True

到此这篇关于Python对称的二叉树多种思路实现方法的文章就介绍到这了,更多相关Python对称的二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • java 对称二叉树的判断

    1. 题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 2. 解题思路 可以按照类似层次遍历,来判断是否是堆成二叉树: 首先根节点以及其左右子树,左子树的左子树和右子树的右子树相同,以及左子树的右子树和右子树的左子树相同即可,然后采用递归一直判断下去. 3. 代码 public class isSymmetrical { public static void main(String[] args) { // 新建一棵二叉搜索

  • PHP实现判断二叉树是否对称的方法

    本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解 递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func

  • Python对称的二叉树多种思路实现方法

    对称二叉树的含义非常容易理解,左右子树关于根节点对称,具体来讲,对于一颗对称二叉树的每一颗子树,以穿过根节点的直线为对称轴,左边子树的左节点=右边子树的右节点,左边子树的右节点=左边子树的左节点.所以对称二叉树的定义是针对一棵树,而判断的操作是针对节点,这时可以采取由上到下的顺序,从根节点依次向下判断,只需要重复调用函数,不需要回溯. 题目:对称的二叉树题: 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的 解题思路一:先遍历右子节点再

  • Python实现重建二叉树的三种方法详解

    Python实现重建二叉树的三种方法详解

    本文实例讲述了Python实现重建二叉树的三种方法.分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字符串递归解析重建 前序遍历顺序字符串堆栈解析重建 如果懒得去看后面的内容,可以直接点击此处本站下载完整实例代码. 思路 学习算法中,python 算法方面的资料相对较少,二叉树解析重建更少,只能摸着石头过河. 通过不同方式遍历二叉树,可以得出不同节点的排序.那么,在已知节点排序的前提下,通过某种遍历方式,可以将排序进行解析

  • Python 剪绳子的多种思路实现(动态规划和贪心)

    剑指Offer(Python多种思路实现):剪绳子 面试14题: 题目:剪绳子 题:给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,且n>1,m>1),每段绳子的长度记为k[0],k[1],k[2],...,k[m].请问k[0]*k[1]*...*k[m]可能的最大乘积是多少?例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积为18. 解题思路一:基于动态规划和贪婪算法. class Solution: def MaxProductAfterCut

  • Python二叉树定义与遍历方法实例分析

    本文实例讲述了Python二叉树定义与遍历方法.分享给大家供大家参考,具体如下: 二叉树基本概述: 二叉树是有限个元素的几个,如果为空则为空二叉树,或者有一个结点称之为根节点,分列根节点两侧的为二叉树的左右子节点,二叉树有如下的性质: 1. 二叉树的每个结点不存在度大于2的结点 2. 二叉树的第i层至多有2^{i-1}个结点 3. 深度为k的二叉树至多有2^k - 1个结点 4. 二叉树中,度为0的结点数N0比度为2的结点数N2大1,即存在N2 + 1 = N0 Python代码: #codin

  • Python模拟登录的多种方法(四种)

    正文 方法一:直接使用已知的cookie访问 特点: 简单,但需要先在浏览器登录 原理: 简单地说,cookie保存在发起请求的客户端中,服务器利用cookie来区分不同的客户端.因为http是一种无状态的连接,当服务器一下子收到好几个请求时,是无法判断出哪些请求是同一个客户端发起的.而"访问登录后才能看到的页面"这一行为,恰恰需要客户端向服务器证明:"我是刚才登录过的那个客户端".于是就需要cookie来标识客户端的身份,以存储它的信息(如登录状态). 当然,这也

  • python循环嵌套的多种使用方法解析

    这篇文章主要介绍了python循环嵌套的多种使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 使用循环嵌套来获取100以内的质数 #!/usr/bin/python # -*- coding: UTF-8 -*- num=[]; i=2 for i in range(2,100): j=2 for j in range(2,i): if(i%j==0): break else: num.append(i) print(num) 使用嵌

  • python 下载文件的多种方法汇总

    python 下载文件的多种方法汇总

    本文档介绍了 Python 下载文件的各种方式,从下载简单的小文件到用断点续传的方式下载大文件. Requests 使用 Requests 模块的 get 方法从一个 url 上下载文件,在 python 爬虫中经常使用它下载简单的网页内容 import requests # 图片来自bing.com url = 'https://cn.bing.com/th?id=OHR.DerwentIsle_EN-CN8738104578_400x240.jpg' def requests_downloa

  • python之多种方式传递函数方法案例讲解

    这篇文章主要介绍了python进阶教程之函数参数的多种传递方法,包括关键字传递.默认值传递.包裹位置传递.包裹关键字混合传递等,需要的朋友可以参考下 我们已经接触过函数(function)的参数(arguments)传递.当时我们根据位置,传递对应的参数.我们将接触更多的参数传递方式. 回忆一下位置传递: def f(a,b,c): return a+b+c print(f(1,2,3)) 在调用f时,1,2,3根据位置分别传递给了a,b,c. 关键字传递 有些情况下,用位置传递会感觉比较死板.

  • Python读取文件内容为字符串的方法(多种方法详解)

    以下笔记是我在 xue.cn 学习群之数据分析小组所整理分享的心得.相关背景是:我选择中文词频统计案例作为考察大家python基础功掌握程度. 以小见大,下面是2个小技能的具体实战: 如何灵活地处理文件读取 如何把数据处理为自己想要的数据类型 方法1: 拷贝文章时,直接把内容赋值给一个变量,保存到一个 .py 文件中.然后在脚本中,导入它. 存储文章的文件 article.py content = """ 复制的文章内容 """ 存储脚本的文件 

  • Python中的二叉树查找算法模块使用指南

    python中的二叉树模块内容: BinaryTree:非平衡二叉树  AVLTree:平衡的AVL树  RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree  FastAVLTree  FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py

随机推荐