遍历算法：二叉树最大深度的解题思路

要计算二叉树的最大深度，至少需要将树中的每个叶子节点都访问一遍，前面学的二叉树的深度优先搜索算法就派上了用场。

def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 # 叶子节点的深度为 0 left_max_depth = self.maxDepth(root.left) # 计算左子树深度 right_max_depth = self.maxDepth(root.right) # 计算右子树深度 tree_max_depth = max(left_max_depth, right_max_depth) + 1 return tree_max_depth # 计算并返回树节点深度

但是具体该用先序遍历、中序遍历还是后序遍历来实现呢？

下面给出了参考步骤；

1. 二叉树的最大深度为左子树的最大深度和右子树的最大深度中的最大值再加一。

2. 要计算当前二叉树的最大深度就必须提前知道左右子树的最大深度。

3. 先访问左右子树，再访问根节点，所以应该使用后序遍历。

我们在动画中了解一下这个过程：

动画中绿色节点代表当前正在参与搜索的子树，蓝色节点代表已经计算出最大深度的子树，而橙色节点代表在最大深度路径上的节点。