题目描述

[EN | CN]

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

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

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

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

1
2
3
4
5
3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3。

解法 1:递归

一课树的深度为左右字数的最大深度加一。

假设结点数为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(\log_2n)$,数的深度。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return 0 if not root else (max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1)
  • 执行用时:52 ms,在所有 Python3 提交中击败了 68.51% 的用户。
  • 内存消耗:15.5 MB,在所有 Python3 提交中击败了 5.55% 的用户。