汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

二叉树的最大深度

发表于 分类于 Valine：
本文字数： 929 阅读时长 ≈ 1 分钟

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3

/
9 20
/
15 7
返回它的最大深度 3 。

层序遍历

也就是广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        if not root:
            return ans
        queue = collections.deque()
        queue.append((root, 1))
        while queue:
            ans += 1
            for i in range(len(queue)):
                p, _ = queue.popleft()
                if p.left:
                    queue.append((p.left, 1))
                if p.right:
                    queue.append((p.right, 1))
        return ans



深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        if not root:
            return ans
        left_level = self.maxDepth(root.left)
        right_level = self.maxDepth(root.right)
        return max(left_level, right_level)+1
坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------