Python3实现二叉树的最大深度
问题提出:
给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
解决思路:递归法求解。从根结点向下遍历,每遍历到子节点depth+1。
代码实现( ̄▽ ̄):
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def maxDepth(self, root: TreeNode) -> int: if root==None: return 0 count = self.getDepth(root,0) return count def getDepth(self,node,count): if node!=None: num1 = self.getDepth(node.left,count+1); num2 = self.getDepth(node.right,count+1); num = num1 if num1>num2 else num2 return num else: return count
时间和空间消耗:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
python二叉树遍历的实现方法
复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class TreeNode(object): def __init__(self,data=0,left=0,right=0): self.data = data self.left = left self.right = right class BTree(object): def __init__(self,root=0):
-
python实现的二叉树算法和kmp算法实例
主要是:前序遍历.中序遍历.后序遍历.层级遍历.非递归前序遍历.非递归中序遍历.非递归后序遍历 复制代码 代码如下: #!/usr/bin/env python#-*- coding:utf8 -*- class TreeNode(object): def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right =
-
python数据结构树和二叉树简介
一.树的定义 树形结构是一类重要的非线性结构.树形结构是结点之间有分支,并具有层次关系的结构.它非常类似于自然界中的树.树的递归定义:树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点:(2)其余的结点可分为m(m≥0)个互不相交的子集Tl,T2,-,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subree). 二.二叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合.每个结点最多有两个子树的有序树
-
python数据结构之二叉树的统计与转换实例
一.获取二叉树的深度 就是二叉树最后的层次,如下图: 实现代码: 复制代码 代码如下: def getheight(self): ''' 获取二叉树深度 ''' return self.__get_tree_height(self.root) def __get_tree_height(self, root): if root is 0: return 0 if root.left is 0 and root.righ
-
Python探索之创建二叉树
问题 创建一个二叉树 二叉树有限多个节点的集合,这个集合可能是: 空集 由一个根节点,和两棵互不相交的,分别称作左子树和右子树的二叉树组成 创建二叉树,创建节点,再创建节点之间的关系 Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, right
-
Python简单定义与使用二叉树示例
本文实例讲述了Python简单定义与使用二叉树的方法.分享给大家供大家参考,具体如下: class BinaryTree: def __init__(self,rootObj): self.root = rootObj self.leftChild = None self.rightChild = None def insertLeft(self,newNode): if self.leftChild == None: self.leftChild = BinaryTree(newNode) e
-
Python利用前序和中序遍历结果重建二叉树的方法
本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''
-
python二叉树的实现实例
树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱.树的递归定义如下:(1
-
python实现的二叉树定义与遍历算法实例
本文实例讲述了python实现的二叉树定义与遍历算法.分享给大家供大家参考,具体如下: 初学python,需要实现一个决策树,首先实践一下利用python实现一个二叉树数据结构.建树的时候做了处理,保证建立的二叉树是平衡二叉树. # -*- coding: utf-8 -*- from collections import deque class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=l
-
Python中的二叉树查找算法模块使用指南
python中的二叉树模块内容: BinaryTree:非平衡二叉树 AVLTree:平衡的AVL树 RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree FastAVLTree FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py
随机推荐
- 手机Web APP如何实现分享多平台功能
- 从每个分类选择10条记录的sql语句
- JavaScript 判断浏览器类型及版本
- ASP.NET(C#)实现一次性动态上传多张图片的代码(多个文件)
- 基于python的字节编译详解
- Android图片三级缓存策略(网络、本地、内存缓存)
- MySQL压测工具mysqlslap的介绍与使用
- MySQL触发器运用于迁移和同步数据的实例教程
- Jquery与Bootstrap实现后台管理页面增删改查功能示例
- c语言中用位运算实现加法技巧介绍
- 完美解决liunx下dns配置重启失效的问题
- 使用OpenGL实现3D立体显示的程序代码
- SEO优化之URL优化
- 主题越小,网站用户粘度越高
- SOHO的无线组网2
- vue init失败简单解决方法(终极版)
- Vue渲染过程浅析
- js中的闭包实例展示
- 使用wxapp-img-loader自定义组件实现微信小程序图片预加载功能
- pyqt5 使用label控件实时显示时间的实例