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

时间和空间消耗：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 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二叉树的实现实例

    树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱.树的递归定义如下:(1

  • 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数据结构之二叉树的统计与转换实例

    一.获取二叉树的深度 就是二叉树最后的层次,如下图: 实现代码: 复制代码 代码如下: 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利用前序和中序遍历结果重建二叉树的方法

    本文实例讲述了Python利用前序和中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 这道题比较容易,前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左.右子树即可.示意图如图所示: 利用前序和中序遍历的结果重建二叉树 Python代码: # coding: utf-8 ''

  • python数据结构树和二叉树简介

    一.树的定义 树形结构是一类重要的非线性结构.树形结构是结点之间有分支,并具有层次关系的结构.它非常类似于自然界中的树.树的递归定义:树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点:(2)其余的结点可分为m(m≥0)个互不相交的子集Tl,T2,-,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subree). 二.二叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合.每个结点最多有两个子树的有序树

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

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

  • 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实现的二叉树定义与遍历算法实例

    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代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): def __init__ (self, data, left = None, right

随机推荐