111. 二叉樹的最小深度
難度簡(jiǎn)單689
給定一個(gè)二叉樹勉盅，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量顶掉。
說(shuō)明：葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)草娜。
圖一
第一次錯(cuò)誤解法：
這種解法無(wú)法解決如下圖中的情況
image.png
這種情況下，返回的答案是1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
else:
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
第二次錯(cuò)誤
修改以上錯(cuò)誤一喘，把節(jié)點(diǎn)為空時(shí)的返回值變大（私以為比1大即可驱还，但是后續(xù)發(fā)現(xiàn)是錯(cuò)誤的），
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 100
if not root.left and not root.right:
return 1
else:
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
我的最終解法：
提交之后凸克，發(fā)現(xiàn)有個(gè)結(jié)構(gòu)如圖一议蟆，但是有1800多個(gè)節(jié)點(diǎn)的用例，沒(méi)有通過(guò)萎战，返回值是101咐容，這時(shí)候我才意識(shí)到，節(jié)點(diǎn)空時(shí)的返回值不是比1大即可蚂维，隨著遞歸的進(jìn)行戳粒，必須要比最深層那個(gè)空節(jié)點(diǎn)返回值大才行路狮，那么就無(wú)窮大啦！
另外蔚约，第一次根節(jié)點(diǎn)為空的情況沒(méi)法判斷了奄妨，改成子函數(shù)形式。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
def minDepthFun(root):
if not root:
return float('inf') # 設(shè)置為無(wú)窮大
if not root.left and not root.right:
return 1
else:
return 1 + min(minDepthFun(root.left), minDepthFun(root.right))
if not root:
return 0
else:
return minDepthFun(root)
官方解法
官方解法的關(guān)鍵在于苹祟，將左右節(jié)點(diǎn)為空的情況分別討論砸抛，分別遞歸
深度優(yōu)先遍歷
對(duì)于每一個(gè)非葉子節(jié)點(diǎn)，我們只需要分別計(jì)算其左右子樹的最小葉子節(jié)點(diǎn)深度树枫。這樣就將一個(gè)大問(wèn)題轉(zhuǎn)化為了小問(wèn)題直焙，可以遞歸地解決該問(wèn)題。
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = 10**9
if 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
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有砂轻。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)奔誓，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
廣度優(yōu)先遍歷
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
que = collections.deque([(root, 1)])
while que:
node, depth = que.popleft()
if not node.left and not node.right:
return depth
if node.left:
que.append((node.left, depth + 1))
if node.right:
que.append((node.right, depth + 1))
return 0
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有搔涝。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)厨喂，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
