给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径土的节点数。说明:叶子节点是指没有子节点的节点。示例: 给定二叉树[3,9,20,null,null,15,7] 返回它的最大深度3.
时间: 2024-09-21 13:11:00 浏览: 32
给定一个二叉树的最大深度问题,可以使用递归算法来解决。从根节点开始,对于每个节点,计算其左子树和右子树的最大深度,然后取两者中的较大值加一,即为当前节点所在的高度。由于二叉树的特点,最大的深度就是从根节点到最深叶子节点的距离。
以下是 Python 中的一个实现例子:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 计算最大深度的函数
def maxDepth(root):
if root is None:
return 0
else:
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
# 返回左右子树的最大深度加上当前节点,即为当前高度
return max(left_depth, right_depth) + 1
# 示例二叉树构造
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.left.left = TreeNode(15)
root.right.right = TreeNode(7)
# 打印最大深度
print(maxDepth(root)) # 输出:3
```
这个代码首先检查根节点是否为空,如果为空则返回深度为0;否则分别递归计算左子树和右子树的最大深度,最后返回两者中的较大值加一作为当前节点的最大深度。
阅读全文