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.
class Solution: # @param root, a tree node # @return an integer minDep =-1 def minDepth(self, root): if root is None: return 0 self.helper(root,1) return self.minDep # @param dep, 当前为第几层 def helper(self,root,dep): if root.left is None and root.right is None: if self.minDep is -1: self.minDep =dep elif self.minDep >dep: self.minDep =dep if dep >= self.minDep and self.minDep is not -1: return False if root.left is not None: self.helper(root.left,dep+1) if root.right is not None: self.helper(root.right,dep+1)
这题我使用的是DFS，但是我设置了一个minDep的global变量。这个变量储存目前最小的【叶子节点到根的距离】，所以其他分支遍历的时候，检查一下dep（当前距离）是否大于minDep，如果大于或者等于，就结束该分支的遍历。
[leetcode] Minimum Depth of Binary Tree ,到叶子节点的最小距离 （python）
原文：http://www.cnblogs.com/zhidan/p/3975354.html