题解 | #二叉树的最小深度#
二叉树的最小深度
https://www.nowcoder.com/practice/6a7f40d7696d46f79c74c61179993be6
解答：与求二叉树的最大深度有异曲同工之妙，均用后序遍历来做，但是最大深度是返回max(l,r)+1，而此题思考题意，要分3种情况，①当左右子树均为0则返回1，②当左右子树中有一个为0，则返回其中不为0的那个并且+1，③当左右子树均不为0则返回min(l,r)+1。因为遍历了所有结点所以时间复杂度O(n)，空间复杂度O(1)。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int run(TreeNode* root) {
// write code here
if(root==NULL)return 0;
return dfs(root);
}
int dfs(TreeNode* root){
if(root==NULL)return 0;
//叶子结点判断
int l=dfs(root->left);
int r=dfs(root->right);
int tmp;
if(l==0&&r==0){
tmp=0;
}
else if(l!=0&&r==0){
tmp=l;
}
else if(l==0&&r!=0){
tmp=r;
}
else{
tmp=min(l,r);
}
return tmp+1;
}
};
投递数字广东等公司7个岗位 >
查看3道真题和解析