网站后台使用培训北京疫情最新新闻

题目

给定一个二叉树 root ，返回其最大深度。

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

思路与算法

树的最大深度可以通过其左子树和右子树的最大深度来定义。对于给定节点，最大深度为 1（当前节点）加上其左子树和右子树的最大深度中的最大值。

1. base case(s):如果树是空的（即当前节点是 None ），则最大深度为 0。
2. 递归步骤：maxDepth(node)=1+max(maxDepth(node.left),maxDepth(node.right))

代码

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

总结

base cases对于防止无限递归和处理空节点至关重要。