111. Minimum Depth of Binary Tree
一、问题描述
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.
二、输入输出
三、解题思路
递归
这种题用递归调用会非常简单。首先分情况讨论root == NULL 直接返回0如果root->left 和 root->right 全部为NULL 返回1如果left right有一个不为空，一个为空，返回 1 + minDepth(不为空的分支)如果left right都不为空，返回 1+ min(minDepth(left), minDepth(right))
/**
* 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 minDepth(TreeNode* root) {
if(root == nullptr)return
0;
else if(root->
left == nullptr && root->
right == nullptr)return
1;
else if(root->
left != nullptr && root->
right == nullptr) return
1 + minDepth(root->
left);
else if(root->
left == nullptr && root->
right != nullptr) return
1 + minDepth(root->
right);
else return
1 + std::min(minDepth(root->
left), minDepth(root->
right));
}
};
