难度: Easy
某公司架构以二叉树形式记录，请返回该公司的层级数。
示例 1：
输入：root = [1, 2, 2, 3, null, null, 5, 4, null, null, 4] 输出: 4 解释: 上面示例中的二叉树的最大深度是 4，沿着路径 1 -> 2 -> 3 -> 4 或 1 -> 2 -> 5 -> 4 到达叶节点的最长路径上有 4 个节点。
提示：
节点总数 <= 10000注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
运行时间: 56 ms
内存: 16.5 MB
# 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:
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
该题解采用递归方法来计算二叉树的最大深度。它首先检查当前的树节点是否为 None，如果是，则当前深度为0。如果不是，它递归地计算左子树和右子树的最大深度，取两者中的较大值，然后加上当前的根节点（加1），最终返回这个值作为整棵树的最大深度。
时间复杂度: O(n)
空间复杂度: O(n)（最坏情况），O(log(n))（平均情况）
# 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:
# 如果当前节点为空，则返回深度0
if root is None:
return 0
# 递归地计算左子树和右子树的最大深度，然后取最大值，再加上当前根节点
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
递归方法在处理树结构问题时比较直观和自然，因为它可以直接按树的定义（一个节点加上它的子树）来处理问题。每一次递归调用都是对一个子问题的处理，这与树结构的递归性质非常吻合。虽然迭代方法也可以使用，如利用层序遍历计算树的深度，但这通常需要额外的数据结构（例如队列）来跟踪节点层级，实现上不如递归直接和简洁。
对于非常深的二叉树，递归方法确实有栈溢出的风险。为了优化，可以考虑使用迭代方法，如层序遍历，这种方法不依赖于调用栈，而是使用队列来处理每一层的节点。如果仍需使用递归，可以尝试增加Python的递归限制（通过sys.setrecursionlimit()函数），或者重写递归为尾递归形式，虽然Python默认不优化尾递归。
在递归解法中，空节点表示树的一个终点。处理空节点的方法是在递归函数中首先检查节点是否为None。如果是None，递归应当返回0，表示没有子树的深度。这样确保了只有非空节点才会贡献到树的总深度中，从而确保计算的准确性。
在标准的二叉树深度计算问题中，每个节点的左右子树深度只会被计算一次，因此使用缓存并不会带来性能优势。但在一些变体问题中，比如多次查询不同节点的深度，可以使用哈希表或其他缓存技术来存储已计算过的节点深度，从而避免重复计算，提高效率。