二叉樹最小深度

求二叉樹最小深度

Day47: 題目

給定一個(gè)二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例:

給定二叉樹 [3,9,20,null,null,15,7],

返回它的最小深度 ?2.

補(bǔ)全下面代碼：

#?Definition?for?a?binary?tree?node.
#?class?TreeNode(object):
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.left?=?None
#?????????self.right?=?None

class?Solution(object):
????def?minDepth(self,?root):
????????"""
????????:type?root:?TreeNode
????????:rtype:?int
????????"""

2 分析

分析過程的開始，我們先看一個(gè)錯(cuò)誤的求解，并說明為什么它是錯(cuò)誤的：

class?Solution(object):
????def?minDepth(self,?root):
????????"""
????????:type?root:?TreeNode
????????:rtype:?int
????????"""
????????if?not?root:
????????????return?0?
????????if?not?root.left?and?not?root.right:
????????????return?1
????????return?1?+?min(self.minDepth(root.left),self.minDepth(root.right))

考慮下面二叉樹：

使用以上代碼返回最小深度為 1，其實(shí)最小深度為 2，因?yàn)樽钚∩疃鹊亩x為：從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

為什么上面的解有問題呢？

原因在于遞歸基選取有問題，只考慮了下面兩種情況：

1. 二叉樹為 None
2. 二叉樹只有一個(gè)節(jié)點(diǎn)

遞歸基未考慮下面兩種情況，所以導(dǎo)致出錯(cuò)：

3

正確的求解，需要把上面遺漏的兩種遞歸基考慮進(jìn)去:

????????#?遞歸基的下面兩種情況必須考慮進(jìn)去：????
????????if?not?root.left:
????????????return?1?+?self.minDepth(root.right)
????????if?not?root.right:
????????????return?1?+?self.minDepth(root.left)

正確的完整代碼如下：

class?Solution(object):
????def?minDepth(self,?root):
????????if?not?root:
????????????return?0?
????????if?not?root.left?and?not?root.right:
????????????return?1
????????????
????????#?遞歸基的下面兩種情況必須考慮進(jìn)去：????
????????if?not?root.left:
????????????return?1?+?self.minDepth(root.right)
????????if?not?root.right:
????????????return?1?+?self.minDepth(root.left)

????????return?1?+?min(self.minDepth(root.left),self.minDepth(root.right))