111.二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
思路
方法一：深度优先搜索
首先可以想到使用深度优先搜索的方法，遍历整棵树，记录最小深度。
对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。
方法二：广度优先搜索
使用广度优先搜索的方法，遍历整棵树。
当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
代码
# Definition for a binary tree node.
import collections
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def minDepth(self, root):
"""
深度优先搜索
:type root: TreeNode
:rtype: int
"""
def get_depth(root):
if root is None:
return 0
left_depth = get_depth(root.right)
right_depth = get_depth(root.left)
return min(right_depth, left_depth) + 1
return get_depth(root)
def minDepth1(self, root):
"""深度优先搜索"""
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.minDepth1(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth1(root.right), min_depth)
return min_depth + 1
def minDepth2(self, root):
"""深度优先搜索"""
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
def create_binary_tree(self, nodes_list):
node1 = TreeNode(nodes_list[1])
node3 = TreeNode(nodes_list[3])
node4 = TreeNode(nodes_list[4])
node2 = TreeNode(nodes_list[2], node3, node4)
root = TreeNode(nodes_list[0], node1, node2)
return root
if __name__ == "__main__":
slt = Solution()
root = slt.create_binary_tree([3, 9, 20, 15, 7])
print(slt.minDepth(root))