如何計算二叉樹的最小深度

這是來自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！這使我很困惑......

來源

2015-04-07 user12551

well..i不知道爲什麼，這個數字並不show..Here就是我的意思：根是8，其左孩子是3，右孩子10.And 3有其左子1 .. ..謝謝 – user12551

代碼是否可能解釋了只有一個根深度爲1的樹？所有的路徑都會比您期望的多返回1嗎？ – AndyG

我看着兩個代碼塊，他們似乎返回2（如預期）。當然，我不是Python解釋器，我懶得去運行代碼，所以我不能肯定地說，但是......看起來你錯了那些解決方案的回報。你的問題到底是什麼？ – Shashank

深度優先搜索或深度優先搜索都可以找到離根最近的葉。 BFS可以比在整個樹上搜索更快（這對於DFS是必要的），儘管它通常會使用更多的內存。

下面是兩個實現的完整示例，這兩個實現都返回樹的最小深度以及處於該最小深度的葉節點。深度優先比寬度優先更容易實現，因爲使用遞歸表示深度優先算法很容易。

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)

來源

2015-04-07 04:27:47

如何計算二叉樹的最小深度

回答

相關問題