要计算二叉树的最大深度至少需要将树中的每个叶子节点都访问一遍前面学的二叉树的深度优先搜索算法就派上了用场。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. 先访问左右子树再访问根节点所以应该使用后序遍历。我们在动画中了解一下这个过程动画中绿色节点代表当前正在参与搜索的子树蓝色节点代表已经计算出最大深度的子树而橙色节点代表在最大深度路径上的节点。
