[LeetCode] 104. 二叉树的最大深度 (Maximum Depth of Binary Tree)

题目描述

给定一个二叉树，找出其最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数。

解题思路

递归计算左右子树的最大深度，取较大值加 1。

• 时间复杂度： O(n)
• 空间复杂度： O(h)，h 为树的高度

代码实现

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

总结

二叉树问题的天然解法是递归。理解递归的终止条件和递推关系是关键。