本节学习深度优先算法在树中的一个典型应用--求二叉树的最大深度问题.
问题描述:
给定一棵二叉树,求其的最大深度.最大深度是指二叉树的根节点与最远的叶子节点之间的高度.
思路解析:
思考如何能求得二叉树的最大深度,对于根节点来说,选择其左右子树中较深的子树深度再加上根节点这一层的深度1,即为这颗二叉树的最大深度.可见,可以将原问题拆分拆分成不断求子树深度的问题.求子树深度可以视为原始问题的子问题,在解决规模较大的问题前,需要先解决规模较小的子问题.变量如下:
root变量:表示给定二叉树的根节点
通过递归调用的方式,当节点为空时,将0返回上层,也相当是递归的终止条件.当节点不为空时,将以该节点为根节点的子树深度值返回给上层,最终返回给定二叉树的最大深度,即求出左右二叉树中深度较大的值加上1
完整代码如下:
def maxDepth(root):# 如果根节点不存在（即树为空），返回0if not root:return 0else:# 递归计算左子树的最大深度left_depth = maxDepth(root.left)# 递归计算右子树的最大深度right_depth = maxDepth(root.right)# 返回左右子树最大深度的较大值加1（当前节点的深度）return max(left_depth, right_depth) + 1
