原題

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

?

思路一

• 類似于求最大深度時的遞歸思路
• 不過需要注意的是當某一節點的左子節點(右子節點類似)為空時，不應該參與最小值的比較（否則一定為最小，但是他并不是葉子節點），所以需要返回該節點的右子節點的最小深度

?

代碼實現

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None# 與求最大深度類似，不過需要注意的是當某一節點左子節點(右子節點類似)有為空的情況時 # 應該不參與最小值的比較，需要返回該節點的右子節點的最小深度 # 這里通過返回right + left + 1簡化上述思路 class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""return self.helper(root)def helper(self, node):if node == None:return 0left = self.helper(node.left)right = self.helper(node.right)return min(right, left) + 1 if (right and left) else right + left + 1

　　

思路二

• 采用正向計數的遞歸思想

?

代碼實現

# 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"""return self.dfs(root,0)def dfs(self,x,level):if x==None:return levelif x.left==None and x.right==None:return level+1if x.left!=None and x.right==None:return self.dfs(x.left,level+1)if x.left==None and x.right!=None:return self.dfs(x.right,level+1)return min(self.dfs(x.left,level+1),self.dfs(x.right,level+1))

　　

?

轉載于:https://www.cnblogs.com/LiCheng-/p/6862378.html

總結

以上是生活随笔為你收集整理的LeetCode 111. Minimum Depth of Binary Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。