Python3实现二叉树的最大深度

yipeiwu_com6年前Python基础

问题提出:

给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

解决思路:递归法求解。从根结点向下遍历,每遍历到子节点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设计】。

相关文章

python实现的AES双向对称加密解密与用法分析

本文实例讲述了python实现的AES双向对称加密解密与用法。分享给大家供大家参考,具体如下: 高级加密标准(Advanced Encryption Standard,AES),在密码学...

python Manager 之dict KeyError问题的解决

程序需要多进程见共享内存,使用了Manager的dict。 最初代码如下: from multiprocessing import Process, Manager d = Mana...

numpy 返回函数的上三角矩阵实例

numpy 返回函数的上三角矩阵 np.triu() matrix2=np.triu(matrix1) numpy.triu(m, k=0)[source] Upper tri...

Python编程对列表中字典元素进行排序的方法详解

本文实例讲述了Python编程对列表中字典元素进行排序的方法。分享给大家供大家参考,具体如下: 内容目录: 1. 问题起源 2. 对列表中的字典元素排序 3. 对json进行比较(忽略列...

python机器学习理论与实战(一)K近邻法

python机器学习理论与实战(一)K近邻法

机器学习分两大类,有监督学习(supervised learning)和无监督学习(unsupervised learning)。有监督学习又可分两类:分类(classification...