计算二叉树的最大深度

**计算二叉树的最大深度**

二叉树是一种常见的数据结构，具有左右孩子的每个结点都只有一个父结点。二叉树的最大深度是指从根结点到最远叶结点所经过的路径长度，即树中最长的路径长度。

在计算二叉树的最大深度时，我们需要考虑以下几种情况：

1. 树为空：此时最大深度为0。
2. 树不空：我们需要递归地访问每个结点，直到找到最远叶结点。

**递归算法**

下面是计算二叉树的最大深度的递归算法：

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef max_depth(node):
 """
 计算二叉树的最大深度。

 Args:
 node (Node): 二叉树的根结点。

 Returns:
 int: 二叉树的最大深度。
 """
 if node is None:
 # 树为空，最大深度为0 return0 else:
 # 递归地访问每个结点 left_depth = max_depth(node.left)
 right_depth = max_depth(node.right)

 # 返回较大的深度 return max(left_depth, right_depth) +1# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(max_depth(root)) # 输出：3

def max_depth(node):
 """
 计算二叉树的最大深度。

 Args:
 node (Node): 二叉树的根结点。

 Returns:
 int: 二叉树的最大深度。
 """
 if node is None:
 return0 stack = [(node,1)]
 max_depth =0 while stack:
 current_node, depth = stack.pop()

 if current_node.left is not None or current_node.right is not None:
 if current_node.left is not None:
 stack.append((current_node.left, depth +1))
 if current_node.right is not None:
 stack.append((current_node.right, depth +1))

 max_depth = max(max_depth, depth)

 return max_depth# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print(max_depth(root)) # 输出：3