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.
Solution
(Minimum-Depth-Binary-Tree.py) download
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
27
28
29
30
31
32
| # 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 not root:
return 0
return self.searchTree(root,1)
def searchTree(self, node,level):
if node.left == None and node.right == None:
return level
if node.left and node.right:
return min(self.searchTree(node.left,level+1), self.searchTree(node.right,level+1))
elif node.left:
return self.searchTree(node.left,level+1)
else:
return self.searchTree(node.right,level+1)
|