Q111 Minimum Depth of Binary Tree
Q111 Minimum Depth of Binary Tree
echobingo
发布于 2018-04-25 16:49:05
发布于 2018-04-25 16:49:05
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.
解题思路：
先明白最小路径的定义：从根结点到最近叶子结点的所包含的结点个数（包括根）。
举个例子：
Example1:
0
return 1Example2:
0
/
-3
\
5
return 3Example3:
0
/ \
-3 9
/
5
return 2观察几个例子，发现对于例子2，我们只需要找到最大深度即可；对于例子3，我们只需要找到最小深度即可。而例子2和3的区别就在于根节点的左右子树是否全为非空。如果全为非空，找到最小深度；否则，找到最大深度。
Python实现：
# 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):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
if root.left != None and root.right != None:
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
else:
return max(self.minDepth(root.left), self.minDepth(root.right)) + 1本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.02.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录