欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

minimum-depth-of-binary-tree

程序员文章站 2022-11-08 12:26:53
题目描述: 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 near ......

题目描述:

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 };