首页 > > 程序设计 > C/C++ >

minimum-depth-of-binary-tree

2018-07-25 13:00:45来源：博客园阅读 ()

题目描述：

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.

解题思路：

　　递归解题方法：

　　（1）左儿子与右儿子皆不为NULL。父节点的最小深度，等于左儿子最小深度与右儿子最小深度中最小值加1。

　　（2）两个儿子皆为NULL，此时返回1。

　　（3）左儿子为NULL，返回right son 的最小深度值加一。

　　（4）right son为NULL，返回左儿子的最小深度加一。

代码：

 1 class Solution {
 2 public:
 3     int run(TreeNode *root) {
 4         int lmin = 0;
 5         int rmin = 0;
 6         if (root == NULL)
 7             return 0;
 8         if (root->left == NULL) {
 9             rmin = run(root->right);
10             return rmin + 1;
11         }
12         if (root->right == NULL) {
13             lmin = run(root->left);
14             return lmin+1;
15         }
16         rmin = run(root->right);
17         lmin = run(root->left);
18         return lmin<rmin?lmin+1:rmin+1;
19     }
20 };