今天就跟大家聊聊有关如何求出python二叉树的深度，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
资溪网站建设公司创新互联建站,资溪网站设计制作，有大型网站制作公司丰富经验。已为资溪1000+提供企业网站建设服务。企业网站搭建\外贸营销网站建设要多少钱，请找那个售后服务好的资溪做网站的公司定做！
题目描述
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
题目样例
示例
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
题目思考
解决方案
方案 1
思路
- 我们可以这样构造递归方法: 传入节点, 返回当前节点的深度, 该深度是左右子树的最大深度+1
- 假设叶子节点的深度为 1, 显然根节点的深度就是整个树的最大深度了
复杂度
- 空间复杂度 O(H): H 表示树的高度, 也即递归的栈的消耗
代码
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
# 递归出口, 空节点的情况
return 0
# 当前节点深度是左右子树的最大深度+1
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
# 也可以进一步简化为只需要一行代码..
# return 0 if not root else 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
方案 2
思路
- 如果要求必须用迭代方式实现, 那方案 1 就不行了
- 通过分析题目, 显然这里的深度就是指 BFS 的层数, 所以完全可以利用
剑指 Offer 32 - II. 从上到下打印二叉树 II - leetcode 剑指 offer 系列的做法得出层数, 只是不需要打印出每一层的节点, 只需要统计层数即可. 不清楚的同学可以先看看那道题的思路~
复杂度
代码
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
q = [root]
res = 0
while q:
# 当前层节点数目
curlen = len(q)
for node in q[:curlen]:
# 只追加非空子节点
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
# 队列切片, 开始处理下一层
q = q[curlen:]
# 当前层遍历完毕, 深度+1
res += 1
return res
看完上述内容，你们对如何求出python二叉树的深度有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。
当前标题：如何求出python二叉树的深度
文章出自：
http://cdkjz.cn/article/gossje.html
