首页 > 试题广场 >

二叉树的最大深度

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


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

输入

{1,2}

输出

2
示例2

输入

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

输出

3

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python
牛客414147167号头像 牛客414147167号
class Solution:
    def maxDepth(self , root ):
        if root == None:
            return 0 
        return 1+ max(self.maxDepth(root.left),self.maxDepth(root.right))
发表于 2021-04-21 08:34:55 回复(0)
Python
wengJJ头像 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)
Python
猫牛头像 猫牛 
class Solution:
    def maxDepth(self , root ):
        # write code here
        if not root:
            return 0
        else:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

发表于 2021-03-12 00:33:36 回复(0)
Python
好快の刀头像 好快の刀 
"""
双队列层序遍历
"""
class Solution:
    def maxDepth(self , root ):
        # write code here
        if root is None:
            return 0
        q1 = [root]
        q2 = []
        d = 0
        while True:
            if len(q1) <= 0:
                break
            d += 1
            while len(q1) > 0:
                x = q1.pop(0)
                if x.left is not None:
                    q2.append(x.left)
                if x.right is not None:
                    q2.append(x.right)
            if len(q2) <= 0:
                break
            d += 1
            while len(q2) > 0:
                x = q2.pop(0)
                if x.left is not None:
                    q1.append(x.left)
                if x.right is not None:
                    q1.append(x.right)
        return d

发表于 2021-03-03 16:03:48 回复(0)
Python
崔崔呀头像 崔崔呀
递归解法：
class Solution:
    def maxDepth(self , root ):
        # write code here
        if root==None:
            return 0
        return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))

发表于 2021-01-17 16:34:53 回复(0)
Python
RyuAsuka头像 RyuAsuka 
# 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):
        return len(self.level_order(root))

    def level_order(self, root):
        """
        层序遍历，输出层数即可
        """
        result = []
        if not root:
            return result
        queue = [root]
        while queue:
            size = len(queue)
            v = []
            while size > 0:
                node = queue.pop(0)
                v.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                size -= 1
            if len(v) > 0:
                result.append(v)
        return result
不过不得不说递归还是简洁呀，怎么就老是想不到呢
发表于 2020-09-19 19:38:38 回复(0)
Python
wandering_bai头像 wandering_bai
写了一个python 
class Solution:
    def maxDepth(self , root ):
        # write code here
        if not root:
            return 0
        layer = [root]  #first layer
        res = 0
        while layer:
            res += 1
            newlayer = []  #level traverse
            for node in layer:
                if node.left:
                    newlayer.append(node.left)
                if node.right:
                    newlayer.append(node.right)
            layer = newlayer
        return res

层序遍历的答案，非递归
发表于 2020-06-01 18:40:42 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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