二叉树的最小深度

[编程题]二叉树的最小深度

热度指数：3679 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗节点数为N的二叉树，求其最小深度。最小深度是指树的根节点到最近叶子节点的最短路径上节点的数量。

（注：叶子节点是指没有子节点的节点。）

数据范围：

0<=N<=6000

0<=val<=100

你能使用时间复杂度为O(N)，空间复杂度为O(logN)的解法通过本题吗？

例如当输入{1,2,3,4,5}时，对应的二叉树如下图所示：

可以看出离根节点最近的叶子节点是节点值为3的节点，所以对应的输出为2。

示例1

输入

{1,2,3,4,5}

输出

示例2

输入

{1,#,2,#,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

猪猪侠新新酱

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
 */
 int dfs(struct TreeNode* root){
    if(NULL==root)
       return 0;
    else{
        if(root->left==NULL && root->right!=NULL)
               return dfs(root->right)+1;
        if(root->right==NULL && root->left!=NULL)
               return dfs(root->left)+1;
        if(root->right==NULL && root->left==NULL)
               return 1;
        return (dfs(root->left)<dfs(root->right)?dfs(root->left):dfs(root->right))+1;
    }
 }
int run(struct TreeNode* root ) {
    // write code here
    if(root==NULL)
       return 0;

    // if(root->left==NULL)
    //     return dfs(root->right)+1;
    // if(root->right==NULL)
    //     return dfs(root->left)+1;
    return dfs(root);
    
}

发表于 2023-01-10 23:19:35 回复(0)