题目
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代码
|
|