首页 > 试题广场 >

二叉树的最大深度

[编程题]二叉树的最大深度
  • 热度指数：152723 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）


数据范围：，树上每个节点的val满足
要求： 空间复杂度 ,时间复杂度
示例1

输入

{1,2}

输出

2
示例2

输入

{1,2,3,4,#,#,5}

输出

3

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
想退休的灰太狼天天摸鱼头像 想退休的灰太狼天天摸鱼
递归思想 
int maxDepth(struct TreeNode* root ) {
    if (root == NULL) return 0;
    int a = maxDepth(root->left) + 1;
    int b = maxDepth(root->right) + 1;
    return a > b? a:b;
}


发表于 2025-03-21 16:03:09 回复(0)
C
夜雨潇湘人断肠头像 夜雨潇湘人断肠
int _maxDepth(struct TreeNode* root ) {
    if(root==NULL)
    {
        return 0;
    }
    if(root->left==NULL&&root->right==NULL)
    {
        return 1;
    }
    int left = _maxDepth(root->left);
    int right = _maxDepth(root->right);
    return left>right?left+1:right+1;
}
int maxDepth(struct TreeNode* root ) {
    return _maxDepth(root);
}
发表于 2025-01-31 22:05:08 回复(1)
C
牛客183552821号头像 牛客183552821号
沿用最简单的排序的基础上修改出来
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型
 */
 static int count=0;
 int d=0;
 int order(struct TreeNode* root)
 {
    if(root)
    {
        int p=0,c=0;
        p=order(root->left);
        c=order(root->right);

        return 1+(p>c?p:c);
    }  
    return 0;
 }

int maxDepth(struct TreeNode* root ) {
    // write code here

    return order(root);
}
发表于 2024-03-24 12:32:32 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
int maxDepth(struct TreeNode* root ) {
    int res,resLeft,resRight;
    if(root==NULL) 
        return 0;
    resLeft=maxDepth(root->left);
    resRight=maxDepth(root->right);
    return 1+(resLeft>resRight?resLeft:resRight);
}

发表于 2024-03-16 16:19:51 回复(0)
C
陈让然头像 陈让然 
int maxDepth(struct TreeNode* root ) 
{
    // write code here
    //无左右结点及无深度，返回0
    if(root==NULL)
    {
        return 0;
    }
    else 
    {
        //递归遍历左右节点的深度
        int leftDepth=maxDepth(root->left);
        int rightDepth=maxDepth(root->right);
        //左右深度比较，返回较大的深度，+1（算上跟结点）
        return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
    } 
}

发表于 2023-11-14 20:17:58 回复(0)
C
芸某头像 芸某
递归 
int maxDepth(struct TreeNode* root ) {
    // write code here
    int rtn = 0;
    if(root==NULL){
        return 0;
    }else {
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);    
        rtn = 1 + (left>right?left:right);
    }
    return rtn;
}


发表于 2023-09-21 20:21:59 回复(0)
C
牛客446770844号头像 牛客446770844号 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
 */
 //递归算法
int maxDepth(struct TreeNode* root ) {
    // write code here
    if(root==NULL)
    return 0;//递归到空时，返回0
    int m=maxDepth(root->left);//递归左子树，m++
    int n=maxDepth(root->right);//递归右子树,n++
    if(m>n)
    return m+1;
    else
     return n+1;
}

发表于 2023-06-16 17:30:44 回复(0)
C
木弎头像 木弎 
//递归遍历一层一层往下走，并且每进入下一层进行一次深度的比较，
//最后看记录的最深度就知道二叉树的最深度
int maxdeep=0;//记录当前最深度
int max(int a,int b)
{
    return a>b?a:b;
}
void Tree(struct TreeNode* root,int deep)
{
    if(root==NULL)
    {
        return;
    }
    maxdeep=max(maxdeep,deep);//比较深度
    Tree(root->left,deep+1);//进入下一层左子树，层数加一
    Tree(root->right,deep+1);//进入下一层右子树，层数加一
}
int maxDepth(struct TreeNode* root) 
{
    Tree(root,1);
    return maxdeep;
}

发表于 2022-11-24 23:38:05 回复(0)
C
80后大叔头像 80后大叔

设置2个变量来保存最大深度和当前深度，遇到叶子节点则后退

static int total=0;
static int now = 0;
int maxDepth(struct TreeNode* root ) {
    // write code here
    if(root == NULL) {
        return 0;
    } else {
        now++;
        if(now > total) {
            total=now;
        }
        if(root->left != NULL) {
            maxDepth(root->left);
        }
        if(root->right != NULL) {
            maxDepth(root->right);
        }
            now--;
    }
    return total;
}
发表于 2022-11-04 14:47:43 回复(0)
C
阿金要努力头像 阿金要努力 
int maxDepth(struct TreeNode* root ) 
{
    // write code here
    if (root == NULL)
		return 0;
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

发表于 2022-05-04 01:38:48 回复(0)
C
和覅wEJVB头像 和覅wEJVB
int maxDepth(struct TreeNode* root ) 
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->left==NULL && root->right==NULL)
    {
        return 1;
    }
    int leftDepth=maxDepth(root->left);
    int rightDepth=maxDepth(root->right);
    return leftDepth>rightDepth ?  leftDepth+1:rightDepth +1;
    // write code here
}//用变量分别保存左右子树的最大深度，防止递归时出现错误
发表于 2022-04-26 16:30:16 回复(0)
C
CreatorSY头像 CreatorSY 
static int g_dp;

static void dfs_dp(struct TreeNode *root, int deep) {
    if (root == NULL) {
        if (g_dp < deep)
            g_dp = deep;
        return;
    }
    dfs_dp(root->left, deep + 1);
    dfs_dp(root->right, deep + 1);
}

int maxDepth(struct TreeNode* root ) {
    g_dp = 0;
    dfs_dp(root, 0);

    return g_dp;
}
int maxDepth(struct TreeNode* root ) {
    int rdp, ldp;

    if (root == NULL)
        return 0;

    rdp = maxDepth(root->right);
    ldp = maxDepth(root->left);

    return rdp > ldp ? rdp + 1 : ldp + 1;
}
发表于 2022-01-06 22:45:36 回复(0)
提交观点

问题信息

树 dfs
来自：经典编程练习-简单卷
难度：
18条回答 27424浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的最大深度

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号