LeetCode104二叉树的最大深度
目录
【LeetCode104】二叉树的最大深度
题目
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思路与算法
树的最大深度可以通过其左子树和右子树的最大深度来定义。对于给定节点，最大深度为 1（当前节点）加上其左子树和右子树的最大深度中的最大值。
- base case(s):如果树是空的（即当前节点是 None ），则最大深度为 0。
- 递归步骤：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 0
return 1 + max(self.maxDepth(root.right), self.maxDepth(root.left))
总结
base cases对于防止无限递归和处理空节点至关重要。