首页 > 试题广场 >

二叉树的最大深度

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

热度指数：162333 时间限制：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，点此查看相关信息

算法知识视频讲解

Python

wengJJ

Python

递归，使用普通迭代则每次都需要判断左右节点

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def maxDepth(self , root ):
        # write code here
#         递归 终止条件为到达叶子节点 
        if not root:
            return 0
        left_len = self.maxDepth(root.left)
        right_len = self.maxDepth(root.right)
        return 1+max(left_len,right_len)

发表于 2021-04-20 13:08:18 回复(0)

Java

阿拉要洗澡

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

public class Solution {

public int maxDepth(TreeNode root) {

if(root==null){

return 0;

}

int left=maxDepth(root.left);

int right=maxDepth(root.right);

if(left>right){

return left+1;

}else{

return right+1;

}

发表于 2017-08-24 17:01:12 回复(0)

novo

class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == NULL) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

发表于 2016-04-12 22:21:20 回复(3)

JacobGo！

/*
	 * 解法一：
	 * 递归解法，非常简洁
	 */
	public int maxDepth(TreeNode root) {
		if(root==null)
			return 0;
		return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	
	
	
	/*
	 * 解法二： 使用queue进行层序遍历
	 */
	public int maxDepth_1(TreeNode root) {
		if (root == null)
			return 0;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		int res = 0;
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (node.left != null)
					queue.add(node.left);
				if (node.right != null)
					queue.add(node.right);
			}
			res++;
		}

		return res;
	}

发表于 2017-08-06 10:54:04 回复(1)

StrongYoung

	  public int maxDepth(TreeNode root){
		  if(root==null)
			  return 0;
		  int lDepth = maxDepth(root.left);
		  int rDepth = maxDepth(root.right);
		  return 1+(lDepth>rDepth?lDepth:rDepth);
	  }

发表于 2015-10-02 10:30:25 回复(0)

watson_

递归，两行代码：

public int maxDepth (TreeNode root) {
    if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

发表于 2020-10-28 15:39:26 回复(0)

C++

禁忌十万三千魔导书

int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }

发表于 2024-07-12 12:12:40 回复(1)

Java

Vtech

public class Solution {
    public int maxDepth (TreeNode root) {
        return root==null?0:1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

发表于 2021-10-21 09:02:43 回复(0)

胖十斤换网名的阿琛

class Solution {
public:
    int maxDepth(TreeNode *root) {
        return root ? (max(maxDepth(root->left),maxDepth(root->right)) + 1) : 0;
        
    }
};

发表于 2019-10-08 15:14:28 回复(0)

武培轩

Leetcode#104. Maximum Depth of Binary Tree（二叉树的最大深度）

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    /**
     * 递归
     *
     * @param root
     * [@return](/profile/547241) */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }
    /**
     * 非递归，层次遍历
     *
     * @param root
     * [@return](/profile/547241) */
    public int maxDepth_2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        int start = 0;
        int end = 1;
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            start++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            if (start == end) {
                start = 0;
                end = queue.size();
                depth++;
            }
        }
        return depth;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}

编辑于 2018-09-12 15:55:24 回复(0)

阿诺41

if (root == NULL) { return 0; }
        return 1 + max(maxDepth(root->left), maxDepth(root->right));

发表于 2017-08-29 21:24:05 回复(0)

C++

ZZZ2021

一行即可

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root?1 + max(maxDepth(root->left), maxDepth(root->right)):0;
    }
};

发表于 2023-07-24 10:55:58 回复(0)

cqu后起之秀

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int depth = 0;
    int res = 0;
    int road = 0;
     
    void trasvel(TreeNode* root){
        if(root == NULL) {
            res = max(res, road);
            return;
        }
        road++;
        trasvel(root->left);
        trasvel(root->right);
        road--;
    }
    int maxDepth(TreeNode* root) {
        // write code here
        trasvel(root);
        return res;
    }
};

发表于 2022-03-16 02:29:42 回复(0)

Java

小灰灰QAQ

public class Solution {
    /**
     * 递归还是很简洁的
     * @param root TreeNode类 
     * @return int整型
     */
  public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

发表于 2021-11-23 15:39:30 回复(1)

不想睡觉的白日梦想家

public class Solution {
    public int maxDepth (TreeNode root) {
        return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

发表于 2021-03-24 19:00:02 回复(0)

Java

tornado123

    public int maxDepth (TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

发表于 2020-10-14 09:58:02 回复(0)

金虹桥招财猫

class Solution {
    public int maxDepth(TreeNode root) {
        //在这里递归和迭代时空复杂度一致 递归代码更简洁
        return root == null ? 0 : 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

发表于 2020-07-10 13:32:12 回复(0)

promethus

// 递归版本
class Solution{
public:
    int maxDepth(TreeNode* root) {
       return root == NULL ? 0 : max(maxDepth(root->left),maxDepth(root->right)) +1;
    }
};

// 层序遍历bfs
class Solution{
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while(!que.empty())
        {
            int size = que.size();
            depth++;
            for(int i = 0; i < size; ++i)
            {
                TreeNode* tmp = que.front();
                que.pop();
                if(tmp->left != NULL)
                    que.push(tmp->left);
                if(tmp->right != NULL)
                    que.push(tmp->right);
            }
        }
        return depth;
    }
};

发表于 2019-08-22 10:21:01 回复(0)

我菜得抠脚

    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }

发表于 2018-05-25 20:47:05 回复(4)

C/C++

华科平凡

class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (root==NULL){return 0;}
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

C++ solution

发表于 2017-10-27 09:13:41 回复(0)

提交观点

问题信息

树 dfs

来自：经典编程练习-简单卷

难度：

367条回答 715收藏 29393浏览

通过挑战的用户

查看代码

随机昵称都有什...

2023-02-23 11:54:32
Champ.Ping

2023-02-01 15:39:53
小苏小苏，绝不认输

2022-12-11 22:23:22
是单身的查理斯很野蛮

2022-10-31 14:19:36
牛客65523...

2022-10-08 22:17:00

二叉树的最大深度

输入

输出

输入

输出

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

C++ solution

问题信息

热门推荐

通过挑战的用户

相关试题