[LeetCode]111. 二叉树的最小深度(Minimum Depth of Binary Tree)

题目描述

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

返回它的最小深度 2.

解题思路

  1. 解法一:递归。
  2. 解法二:DFS。
  3. 解法三:BFS。

代码

Python 3.6

解法一:递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def minDepth(self, root: TreeNode) -> int:
if root is None:
return 0

children = [root.left, root.right]
if not any(children):
# 叶子节点
return 1

min_depth = float("inf")
for child in children:
if child is not None:
min_depth = min(min_depth, self.minDepth(child))

return min_depth + 1

执行用时 : 76 ms
内存消耗 : 16.3 MB

解法二:DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def minDepth(self, root: TreeNode) -> int:
if root is None:
return 0

stack, min_depth = [(root, 1)], float("inf")
while stack:
node, depth = stack.pop()
children = [node.left, node.right]

if not any(children):
# 叶子节点
min_depth = min(min_depth, depth)
continue

for child in children:
if child is not None:
stack.append((child, depth + 1))
return min_depth

执行用时 : 72 ms
内存消耗 : 15 MB

解法三:BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def minDepth(self, root: TreeNode) -> int:
if root is None:
return 0

stack = [(root, 1)]
while stack:
node, depth = stack.pop(0)
children = [node.left, node.right]
if not any(children):
return depth
for child in children:
if child is not None:
stack.append((child, depth + 1))

执行用时 : 64 ms
内存消耗 : 14.9 MB

参考

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode/