二叉树的最小深度

最小深度思路解析:

与求最大深度相比,求最小深度就要简单很多,从上向下访问,只要访问到一个叶节点,证明已经到达了与根节点距离最近的叶节点处,此叶节点的深度即为最小深度.借助队列,如果当前节点为叶节点,则返回该节点的深度为最终结果;如果当前节点不满足上述判断且不为空节点,即存在子节点,则将其子节点依次入队.因此,求最小深度的思路十分清晰.代码中的变量如下:

root变量:表示给定二叉树的根节点

queue变量:表示队列

depth变量:表示当前节点的深度,根节点的深度为1

node变量:表示取出的队列头部元素中的节点

有一点不同之处:每个节点入队时,将其所处深度与该节点以元组的方式一同入队,首先将根节点及其深度入队,以供迭代过程的开始.代码如下:

from collections import deque  # 导入deque，用于实现队列def minDepth(root):  # 定义函数minDepth，输入参数为二叉树的根节点rootif not root:  # 如果根节点为空，直接返回0，因为空树的深度为0return 0queue = deque([1, root])  # 初始化一个双端队列，将根节点和它的深度（1）作为队列的第一个元素while queue:  # 当队列不为空时，循环执行depth, node = queue.popleft()  # 从队列中弹出一个元素，包含当前节点的深度和节点本身if node and not node.left and not node.right:  # 如果当前节点是叶子节点（没有左右子节点）return depth  # 返回当前深度，因为找到了最小深度if node:  # 如果当前节点不为空queue.append((depth + 1, node.left))  # 将左子节点和它的深度（当前深度+1）加入队列queue.append((depth + 1, node.right))  # 将右子节点和它的深度（当前深度+1）加入队列