Minimum Depth of Binary Tree
环境：python 3.6，scala 2.11.8
题意
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
分析
此题与二叉树的最大深度类似，DFS 思路如下：
叶子结点的定义是左右子节点都为空的结点；
当根节点左右子节点都为空时，maxDepth 和 minDepth 的当前小遍历会停止；
当根节点左右子节点有一个为空时，maxDepth 和 minDepth 会继续遍历不为空的一侧子节点；
当根节点左右子节点都不为空时，maxDepth 和 minDepth 继续重复上述操作。不同的是最终 maxDepth 返回左右子节点较大深度，minDepth 返回左右子节点较小深度；
BFS 思路则相对好理解：
- 对于同一棵二叉树，相同的是，若该二叉树的非根节点若只有一个子节点，minDepth 和 maxDepth 都要继续寻找；
- 不同的是，遍历过程中，就算遇到叶子节点，maxDepth 会寻找更深的叶子结点，而 minDepth 则可能会提前结束遍历过程；
- 值得一提的是，相较于使用队列，个人认为 scala 写法 minDepthV3 中 的 flatMap 算子的使用更能体现此题的 BFS 思路；
代码
python
import collections
def minDepth(root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
if not root.left and not root.right: return 1 # 没有这个判断不影响结果，只是为了及时返回
if not root.left or not root.right:
return 1 + minDepth(root.left) + minDepth(root.right)
return 1 + min(minDepth(root.left), minDepth(root.right))
def minDepthV2(root):
if not root: return 0
queue = collections.deque([(root, 1)]) # 队列保证节点按层级关系有序出队
while queue:
curr, depth = queue.popleft()
if curr:
if not curr.left and not curr.right:
return depth
queue.append((curr.left, depth + 1))
queue.append((curr.right, depth + 1))
scala
import scala.collection.mutable.Queue
object LC111 {
// 超时 => 超内存
// def minDepth(root: TreeNode): Int = {
// if (root == null) return 0
// if (root.left == null & root.right == null) 1
// if (root.left == null | root.right == null)
// return 1 + minDepth(root.left) + minDepth(root.right)
// 1 + math.min(minDepth(root.left), minDepth(root.right))
// }
def minDepth(root: TreeNode): Int = {
if (root == null) return 0
(root.left, root.right) match {
case (null, null) => 1
case (null, _) => 1 + minDepth(root.right)
case (_, null) => 1 + minDepth(root.left)
case _ => 1 + math.min(minDepth(root.left), minDepth(root.right))
}
}
def minDepthV2(root: TreeNode): Int = {
if (root == null) return 0
val q = Queue[(TreeNode, Int)](root, 1)
while (!q.isEmpty) {
val (curr, depth) = q.dequeue()
if (curr != null) {
if (curr.left == null & curr.right == null) return depth
q.enqueue((curr.left, depth + 1))
q.enqueue((curr.right, depth + 1))
}
}
-1
}
// 层次遍历
def minDepthV3(root: TreeNode): Int = {
def go(currLevel: List[TreeNode]): Int = currLevel.contains(null) match {
case true => 0
case false =>
val nextLevel = currLevel.flatMap{node =>
val childs: List[TreeNode] = List(node.left, node.right).filter(_ != null)
if (childs.isEmpty) List(null)
else childs
}
1 + go(nextLevel)
}
go(List(root))
}
}
最后
欢迎交流和补充
