题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

   		3/ 	\9      20/  \15   7

返回它的最小深度 2.

解题思路

1、
直接深度优先遍历，并在每个叶子节点处进行比较保存最小深度。
仔细观察题目，需要求解的是从根节点到最近叶子节点的最短路径上的节点数量。

   		3

此时3为根节点，同时3也是最近的叶子节点，其最短路径为1

   		3/ 9  

此时3为根节点，9为叶子节点，其最短路径为2 而不是1，因为此时3不是叶子节点

所以对于普通的深度优先遍历，3的左子树深度为2，右子树深度为1， 尽管右子树深度更小，但是其并不是最近叶子节点的最短路径的节点数量。

需要对深度优先搜索做一些小小的改变：
首先讨论两种特殊情况：
1、如果根节点为None，则不需要深度优先遍历，直接返回0
2、如果根节点不为None，但是根节点的左右子树均为None，此时根节点同时也是最近叶子节点，则不需要深度优先遍历，直接返回1
接着讨论深度优先搜索：
因为在每次返回左右子树的最小深度，如果其不存在左/右子树，则此时的最小深度不是最近叶子节点对应的深度，所以只有左/右子树不为空时，执行深度优先遍历。（当左子树为空时，此时最小深度为右子树深度；当右子树为空时，此时最小深度为左子树深度；当左右子树均不为空时，返回其深度的最小值）

2、
使用广度优先搜索同样可以解决该问题，根据广度有限搜索的规则，最先搜索到的叶子节点一定是离根节点最近的

python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0def dfs(root):if root.left==None and root.right==None:  #为叶子节点，返回自己深度 1return 1#在之后讨论不为叶子节点的节点if root.left and root.right==None:   #确定左子树存在dfs_left = dfs(root.left)+1return dfs_leftelif root.right and root.left==None:  #确定右子树存在dfs_right = dfs(root.right)+1return dfs_rightelse: #如果右子树不存在，则最小叶子节点深度就是左子树深度dfs_left = dfs(root.left)+1dfs_right = dfs(root.right)+1return min(dfs_left, dfs_right)min_depth = dfs(root)return min_depth

官方DFS代码

class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0if not root.left and not root.right:return 1min_depth = 10**9if root.left:min_depth = min(self.minDepth(root.left), min_depth)if root.right:min_depth = min(self.minDepth(root.right), min_depth)return min_depth + 1

官方BFS代码

class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0que = collections.deque([(root, 1)])while que:node, depth = que.popleft()if not node.left and not node.right:return depthif node.left:que.append((node.left, depth + 1))if node.right:que.append((node.right, depth + 1))return 0