【leetcode】111. Minimum Depth of Binary Tree（Python & C++）

---

111. Minimum Depth of Binary Tree

题目链接

111.1 题目描述：

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.

111.2 解题思路：

思路一：递归。如果当前节点为空，则返回0；如果当前节点的左右子节点都为空，则返回1；如果左节点为空，右节点不空，则返回1+进入右节点深度计算；如果右节点为空，左节点不空，则返回1+进入左节点深度计算；如果左右节点都不空，则分别进入左右节点深度计算，并返回1+较小深度的那个。

思路二：同思路一差不多，进行了优化。如果当前节点为空，则返回0；计算右节点深度和左节点深度；如果左节点为空，返回1+右节点深度；如果右节点为空，返回1+左节点深度。最后返回1+较少深度的那个。

思路三：同思路二差不多，但是超时了。如果当前节点为空，则返回0；如果左节点为空，返回1+右节点深度；如果右节点为空，返回1+左节点深度。最后返回1+较少深度的那个（这里又递归计算了一遍，存在时间浪费）。

111.3 C++代码：

1、思路一代码（6ms）：

class Solution108 { public: int subdepth(TreeNode *p) { int dep = 1; if (p->left == NULL && p->right == NULL) return 1; else if (p->left == NULL && p->right != NULL) return dep + subdepth(p->right); else if (p->left != NULL && p->right == NULL) return dep + subdepth(p->left); else { int dleft = dep + subdepth(p->left); int dright = dep + subdepth(p->right); return dleft < dright ? dleft : dright; } } int minDepth(TreeNode* root) { if (root == NULL) return 0; return subdepth(root); } };

2、思路二代码（6ms）：

lass Solution108_1 { public: int minDepth(TreeNode* root) { if (root == NULL) return 0; int dl=minDepth(root->left); int dr=minDepth(root->right); if (dl == 0) return dr + 1; if (dr == 0) return dl + 1; return dl < dr ? dl+1 : dr+1; } };

3、思路三代码（超时）

class Solution108_2 {//超时 public: int minDepth(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL) return 1 + minDepth(root->right); if (root->right == NULL) return 1 + minDepth(root->left); return minDepth(root->left)<minDepth(root->right) ? minDepth(root->left)+1 : minDepth(root->right)+1; } };

111.4 Python代码：

2、思路二代码（79ms）

class Solution(object): def minDepth(self, root): """ :type root: TreeNode :rtype: int """ if root==None: return 0 dl=self.minDepth(root.left) dr=self.minDepth(root.right) if dl==0: return 1+dr if dr==0: return 1+dl return 1+min(dl,dr)

---