我要招人

去企业版

首页 > 试题广场 >

二叉树的最大深度

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

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

求给定二叉树的最大深度，

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。

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

数据范围： $0 \le n \le 100000$ ，树上每个节点的val满足 $|val| \le 100$
要求：空间复杂度 $O(1)$ ,时间复杂度 $O(n)$

示例1

输入

{1,2}

输出

示例2

输入

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

输出

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

算法知识视频讲解

查看答案及解析

Daniel_shark

第一种：

void traverse(struct TreeNode* root, int *res, int *depth)

{

if (root == NULL) {

return;

}

(*depth)++;

if (root->left == NULL && root->right == NULL) {

*res = fmax(*res, *depth);

}

traverse(root->left, res, depth);

traverse(root->right, res, depth);

(*depth)--;

}

int maxDepth(struct TreeNode* root) {

int res = 0;

int depth = 0;

traverse(root, &res, &depth);

return res;

}

第二种：

int maxDepth(struct TreeNode* root) {

if (root == NULL) {

return 0;

}

return fmax(maxDepth(root->left) + 1, maxDepth(root->right) + 1);

}

发表于 2025-05-28 16:03:23 回复(0)

想退休的灰太狼天天摸鱼

递归思想

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)

StellarVibes

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)

牛客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)

一个优雅的程序猿

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)

陈让然

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)

芸某

递归

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)

牛客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)

木弎

//递归遍历一层一层往下走，并且每进入下一层进行一次深度的比较，
//最后看记录的最深度就知道二叉树的最深度
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)

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)

阿金要努力

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)

和覅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)

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)