111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
解法1
DFS算法
class Solution:
def minDepth(self, root):
if not root:
return 0
if root.left is None and root.right is None:
return 1
elif not root.left:
return 1+self.minDepth(root.right)
elif not root.right:
return 1+self.minDepth(root.left)
else:
return min(self.minDepth(root.right), self.minDepth(root.left)) + 1
解法2
BFS算法
class Solution:
def minDepth(self, root):
if not root:
return 0
if root.left and root.right:
return min(self.minDepth(root.right), self.minDepth(root.left)) + 1
else:
return max(self.minDepth(root.right), self.minDepth(root.left)) + 1
解法3
思路: 逐层遍历, 用一个list存储每一层的左右子节点, 然后得出最早出现的叶子节点在第几层.
class Solution:
def minDepth(self, root):
if not root:
return 0
nodes = [root]
level = 1
while len(nodes) > 0:
sub_nodes = []
for node in nodes:
if not node.left and not node.right:
return level
if node.left:
sub_nodes.append(node.left)
if node.right:
sub_nodes.append(node.right)
nodes = sub_nodes
level += 1
