题目
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.
思路
最短路径的定义是从root到叶子节点的最少节点数,从root开始递归查找,对于每个节点需要判断子节点的情况:
- 左子节点为空,右子节点不为空:继续查找右子节点
- 左子节点不为空,右子节点为空:继续查找左子节点
- 左右子节点都不为空:分别查找两个子节点并返回两者较小的值
- 左右子节点都为空:直接返回
上述四种情况可以进一步合并,只要考虑一个子节点为空,另一个子节点不为空的特殊情况:因为空节点返回值为0,所以只要将左右两个子节点的返回值相加就可以了;其他情况只要无脑取两个子节点的较小返回值。
1
\
2
/
3
因为要找到叶子节点,对于节点2,不能直接取两个子节点的较小值。
python代码
# 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
"""
if root == None:
return 0
if root.left == None or root.right == None:
return self.minDepth(root.left) + self.minDepth(root.right) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1