首页 > 试题广场 >

二叉树的最大深度

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

热度指数：139289 时间限制：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 3

风软一江山

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        if not root : return 0
        count = 0
        queue = [root]
        while queue:
            temp = []
            count += 1
            for node in queue:
                if node.left : temp.append(node.left)
                if node.right : temp.append(node.right)
            queue = temp
        return count

发表于 2022-07-28 14:13:24 回复(1)

Python 3

JianYue

# 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: TreeNode) -> int:
        if not root:
            return 0
        depth=1
        left = 0
        right = 0
        if root.left:
            left = self.maxDepth(root.left)
        if root.right:
            right = self.maxDepth(root.right)
        if left > right:
            return depth + left
        return depth + right

发表于 2022-07-22 16:24:23 回复(0)

Python 3

来个offer叭！

# 非递归，使用队列
import queue
class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        depth = 0
        if not root: return depth
        q = queue.Queue()
        q.put(root)
        while not q.empty():
            # 当前层的结点个数
            n = q.qsize()
            for i in range(n):
                node = q.get()
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            # 遍历完当前层后，深度+1
            depth += 1
        return depth

发表于 2022-07-21 16:47:45 回复(0)

Python 3

东方佑

# 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: TreeNode) -> int:
        # write code here
        if  root:
        
            return len(self.levelOrder(root))
        else:
            return 0
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        self.val_list=[]
        h=root
#         print(h)
        l=self.get_next_h(h)
        
        while l:
            l=self.get_next_hh(l)
        return self.val_list[:-1]

    def get_next_h(self,x):
        self.val_list.append([x.val])
        return [x.left,x.right]

    def get_next_hh(self,x):

        l_r_list=[]
        val_one=[]
        for one in x: 
            if one:
                val_one.append(one.val)
                if one.left:

                    l_r_list.append(one.left)
                else:
                    l_r_list.append(None)
                if one.right:
                    l_r_list.append(one.right)
                else:
                    l_r_list.append(None)
        self.val_list.append(val_one)
        return l_r_list

发表于 2022-07-12 15:49:28 回复(0)

Python 3

lun__

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
##### wow感觉记住层序遍历，好多都可以在其结果上修改得到！这道题，将层序遍历的结果，返回len(res）就可以了。
## 因为层序遍历是并且排列下来的，一行一行下来的。
class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # write code here
        res = []
        def dfs(root, index):
            if not root : return None
            if len(res) < index:
                res.append([])
            res[index-1].append(root.val)
            if root.left:
                dfs(root.left, index + 1)
            if root.right:
                dfs(root.right, index + 1)
        dfs(root, 1)
        return len(res)

##### 层序遍历的长度 为 二叉树的最大深度 maxDepth 
class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        results = [] 
        if not root: 
            return 0 
        
        from collections import deque  
        que = deque([root])     ## 先进 （每次都需要先进来的是 根节点！！！）
        
        while que: 
            res = [] 
            size = len(que) 
            
            for _ in range(size): 
                cur = que.popleft() ## 先出
                
                res.append(cur.val) 
                
                if cur.left: 
                    que.append(cur.left) 
                if cur.right: 
                    que.append(cur.right) 
            results.append(res) 
        return len(results)

发表于 2022-07-04 09:51:46 回复(0)

Python 3

StevenWqq

BFS

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return 0
        q = [root]
        depth = 0
        while q:
            for i in range(len(q)):
                n = q.pop(0)
                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)
            depth += 1
        return depth

发表于 2022-06-01 22:01:14 回复(0)

Python 3

yifan1997

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left = self.maxDepth(root.left)
            right = self.maxDepth(root.right)
            return max(left,right)+1

发表于 2022-05-22 20:34:48 回复(0)

Python 3

Vivimore

递归
最大深度 = 左右子树的最大深度 + 1

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        depth = max(left, right) + 1
        return depth

发表于 2022-05-16 19:14:53 回复(0)

Python 3

一只兔子的奇幻之旅

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        if not root:
            return 0
        else:
            return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))

发表于 2022-04-25 21:27:14 回复(0)

Python 3

danspace

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # write code here
        if root == None: return 0
        if root.left == None and root.right == None:
            return 1
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

发表于 2022-04-19 10:46:36 回复(0)

Python 3

路痴喵

# 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: TreeNode) -> int:
        # write code here
        n = 0
        if root == None:
            return n
        else:
            left = self.maxDepth(root.left)
            right = self.maxDepth(root.right)
            n = max(left+1, right+1)
        return n

发表于 2022-03-20 17:33:24 回复(0)

Python 3

牛客318213606号

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # write code here
        def pre_order(root):
            if not root:
                return 0
            return 1+max(pre_order(root.left),pre_order(root.right))
        return pre_order(root)

发表于 2022-02-10 10:38:43 回复(0)

Python 3

晓炜98

class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # write code here
        if root == None:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1

发表于 2021-12-13 06:03:58 回复(0)

Python 3

牛客38477449号

class Solution:
    def maxDepth(self , root ):
        # write code here
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

发表于 2021-09-06 17:40:44 回复(0)

Python 3

蒙太奇在秋天

# 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 root != None:
            return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))
        else:
            return 0

发表于 2021-08-28 08:07:52 回复(0)

Python 3

牛客593156630号

# 用的BFS

class Solution:

def maxDepth(self , root ):
if root is None:
return 0
# write code here
Q = []
Q.append(root)
p = 0
while Q:
p += 1
size = len(Q)
for i in range(size):
cur = Q.pop(0)
if cur.left:
Q.append(cur.left)
if cur.right:
Q.append(cur.right)
return p

发表于 2021-08-26 19:12:11 回复(0)

Python 3

牛客35961088号

class Solution:
    def maxDepth(self , root ):
        # write code here
        if not root:
            return 0
        dl = self.maxDepth(root.left)
        dr = self.maxDepth(root.right)
        return max(dl, dr) + 1

发表于 2021-07-28 16:24:35 回复(0)