本文将详细介绍如何使用Python求解二叉树的深度。
一、二叉树的定义
在计算机科学中，二叉树是一种常见的数据结构。它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。其中，每个子节点也是一棵二叉树。
二叉树的深度是指从根节点到最远叶子节点的路径上的节点个数。对于空树来说，深度为0。
二、递归解法
求解二叉树的深度可以使用递归的方法。递归的思想是将问题分解成更小规模的子问题进行求解。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(maxDepth(root)) # 输出 3
在上面的代码中，我们定义了一个TreeNode类来表示二叉树的节点，并使用递归的方式求解二叉树的深度。如果根节点为空，则深度为0。否则，分别求解左子树和右子树的深度，取其中较大值并加1，就得到了整棵二叉树的深度。
三、迭代解法
除了递归方法外，我们还可以使用迭代的方法来求解二叉树的深度。迭代的思想是使用一个栈来保存待处理的节点。
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
depth = 0
stack = [(root, 1)] # 初始节点的深度为1
while stack:
node, d = stack.pop()
depth = max(depth, d)
if node.left:
stack.append((node.left, d + 1))
if node.right:
stack.append((node.right, d + 1))
return depth
# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(maxDepth(root)) # 输出 3
在上面的代码中，我们使用一个栈来保存待处理的节点和它们的深度。初始时，根节点的深度为1。每次从栈中取出一个节点，更新深度，并将其左子节点和右子节点加入栈中，并将它们的深度更新为当前节点的深度加1。直到栈为空，即遍历完整棵二叉树。
四、总结
本文介绍了使用Python求解二叉树深度的两种方法：递归和迭代。递归方法思路简单，但可能造成栈溢出；而迭代方法则避免了栈溢出的问题，但需要额外使用一个栈来保存节点。
根据实际情况，选择适合的方法来求解二叉树深度。