问题描述：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3   / \  9  20    /  \   15   7

返回它的最小深度  2。

思路：

用层序遍历，发现为叶子节点时，返回其所在的层即为最小深度。

方法1：

1 class Solution(object): 2     def minDepth(self, root): 3         """ 4         :type root: TreeNode 5         :rtype: int 6         """ 7         if not root: 8             return 0 9         if not root.left and not root.right:10             return 111         last = 012         front = -113         rear = -114         level = 015         l_list=[]16         l_list.append(root)17         rear += 118         level += 119         while front < rear:        20             front += 121             p = l_list.pop(0)22             if not p.left and not p.right:23                 return level24             if p.left:25                 l_list.append(p.left)26                 rear += 127             if p.right:28                 l_list.append(p.right)29                 rear += 130             if front == last:31                 level += 132                 last = rear

方法2：（递归）当左子树为null时，高度为右子树+1，树的最小高度为左子树最小的高度+1.

1 class Solution(object): 2     def minDepth(self, root): 3         """ 4         :type root: TreeNode 5         :rtype: int 6         """ 7         if root: 8             if root.left==None: 9                 return self.minDepth(root.right)+110             elif root.right==None:11                 return self.minDepth(root.left)+112             else:13                 return min(self.minDepth(root.left),self.minDepth(root.right))+114         else:15             return 0

2018-09-10 19:23:25