Title
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.
Tag: Tree, Deep-first Search, Breadth-first Search
Solution
题意为找到一棵树从根节点到叶子节点的最短距离。
显而易见，需要用递归求解，运用DFS，找到每一个节点到叶子节点的最短距离。
AC代码如下。
AC Code
Method 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int (TreeNode* root) {
if(root == nullptr)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(left == 0 && right == 0)
return 1;
if(left == 0)
left = INT_MAX;
if(right == 0)
right = INT_MAX;
return min(left, right) + 1;
}
};
|
Method 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int (TreeNode* root) {
if(root == nullptr)
return 0;
if(root->left == nullptr && root->right == nullptr)
return 1;
int minDept = INT_MAX;
findMinDept(root, minDept, 1);
return minDept;
}
private:
void findMinDept(TreeNode *root, int &minDept, int dept)
{
if(root == nullptr)
return;
if(root->left == nullptr && root->right == nullptr)
{
minDept = dept > minDept ? minDept : dept;
}
findMinDept(root->left, minDept, dept + 1);
findMinDept(root->right, minDept, dept + 1);
}
};
|
近期评论