本节学习解决广度优先搜索算法在树中的典型应用---求二叉树的最大深度.
问题描述:
给定一棵二叉树,求其最大深度.最大深度是指二叉树的根节点与最远的叶子节点之间的高度.
最大深度思路解析:
广度优先搜素算法的特性使该算法非常适用与逐层搜索,既然是逐层搜索,那么用一个变量累计深度,就可以返回最大深度.
我们依然借助队列结构来完成广度优先搜索,若想用一个变量累计深度,那么每次要访问某一层的所有节点.可想而知,在迭代的while循环中,再嵌套一层while循环用于访问某一层的全部节点之后,对深度变量自增,而后执行下一层循环.变量如下:
Root变量:表示给定二叉树的根节点
Queue变量:表示队列
Tmp变量:表示访问该层时,该层子节点的集合,每次迭代更新tmp为空列表
Ans变量:表示最终返回的最大深度,初始值为0.完整代码如下:
from collections import deque # 导入deque，这是一个双端队列，用于实现队列结构def maxDepth(root): # 定义函数maxDepth，输入参数是二叉树的根节点rootif not root: # 如果根节点为空，说明树是空的，返回深度0return 0ans = 0 # 初始化答案变量ans，用于存储树的最大深度queue = deque([root]) # 创建一个双端队列，并将根节点加入队列while queue: # 当队列不为空时，继续循环tmp = [0] # 创建一个临时列表tmp，用于存储当前层级的节点while queue: # 当队列不为空时，继续处理队列中的节点node = queue.popleft() # 从队列中取出一个节点if node.left: # 如果节点的左子节点不为空tmp.append(node.left) # 将左子节点加入临时列表if node.right: # 如果节点的右子节点不为空tmp.append(node.right) # 将右子节点加入临时列表queue.extend(tmp) # 将临时列表中的节点加入队列，这些节点是下一层级的节点ans += 1 # 每处理完一层，深度ans加1return ans # 返回计算得到的树的最大深度
