如何计算二叉树的最小深度

Question

这是leetcode中的问题：给定一棵二叉树，找到它的最小深度。最小深度是从根节点到最近的叶节点的最短路径上的节点数。如果我没理解错的话，意思是如果我有一棵树

最小深度应该是 2（从节点 8 到 10）。但是，从这两个带有 python 代码的链接： http://codesays.com/2014/solution-to-minimum-depth-of-binary-tree-by-leetcode/ https://gist.github.com/Ray1988/9374678 我编译的结果是 3!!!这让我很困惑.....

Answer 1

无论是深度优先还是深度优先搜索都可以找到离根最近的叶子。 BFS 可以比搜索整棵树快得多（这对于 DFS 是必要的），尽管它通常会使用更多内存。

这是两个实现的完整示例，其中 return 树的最小深度和处于该最小深度的叶节点。深度优先比广度优先更容易实现，因为使用递归很容易表示深度优先算法。

import collections
import heapq

Node = collections.namedtuple('Node', ['v', 'children'])

def min_depth_bfs(root):
    todo = [(1, root)]
    while todo:
        depth, node = heapq.heappop(todo)
        if not node.children: return depth, node
        for c in node.children:
            heapq.heappush(todo, (depth + 1, c))

def min_depth_dfs(node):
    if not node.children: return 1, node
    d, n = min(min_depth_dfs(c) for c in node.children)
    return 1 + d, n

example = Node(8, [Node(3, [Node(1, [])]), Node(10, [])])

print min_depth_dfs(example)
print min_depth_bfs(example)

如何计算二叉树的最小深度

How to calculate the minimum depth of binary tree

python

algorithm

tree