LeetCode 111. Minimum Depth of Binary Tree

题目

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.

分析

求一个二叉树的最小深度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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):
if not root: return 0
d = map(self.minDepth, (root.left, root.right))
return 1 + (min(d) or max(d))
def minDepth1(self, root):
if not root: return 0
d, D = sorted(map(self.minDepth, (root.left, root.right)))
return 1 + (d or D)

点评

简单的递归版本深度优先搜索,一定要注意 1 + (min(d) or max(d)),这个的意思是,如果左右子树都有,那么返回高度最低的那个的高度,如果有两个子树中有一个为空,那么返回高度最大的那个