Python3实现二叉树的最大深度

yipeiwu_com5年前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设计】。

相关文章

Django框架 querySet功能解析

可切片 使用Python 的切片语法来限制查询集记录的数目 。它等同于SQL 的LIMIT 和OFFSET 子句。 >>> Entry.objects.all()...

使用python Telnet远程登录执行程序的方法

如下所示: # -*-coding:utf-8 -*- def do_telnet(Host, username, password, finish, commands):...

python的描述符(descriptor)、装饰器(property)造成的一个无限递归问题分享

分享一下刚遇到的一个小问题,我有一段类似于这样的python代码: 复制代码 代码如下: # coding: utf-8 class A(object):   &nb...

Python 中 -m 的典型用法、原理解析与发展演变

Python 中 -m 的典型用法、原理解析与发展演变

在命令行中使用 Python 时,它可以接收大约 20 个选项(option),语法格式如下: python [-bBdEhiIOqsSuvVWx?] [-c command...

python 设置文件编码格式的实现方法

如果要在python2的py文件里面写中文,则必须要添加一行声明文件编码的注释,否则python2会默认使用ASCII编码。(python3已经没有这个问题了,python3默认的文件编...