给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
时间: 2024-09-14 19:17:05 浏览: 60
在计算机科学中,二叉树是每个节点最多有两个子节点的树结构,通常子节点被称作“左子节点”和“右子节点”。要找出给定二叉树的最大深度,通常可以使用递归方法。
递归方法的基本思想是:
1. 如果当前节点为空,即树为空,那么最大深度为0。
2. 如果当前节点不为空,那么最大深度就是其左右子树最大深度加1(加的1是因为要加上当前节点这一层)。
伪代码可以表示为:
```pseudo
function maxDepth(node):
if node is null:
return 0
else:
left_depth = maxDepth(node.left)
right_depth = maxDepth(node.right)
return max(left_depth, right_depth) + 1
```
在实际编程中,如果使用Python语言,可以这样实现:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def maxDepth(root):
if not root:
return 0
else:
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
```
使用这个函数,就可以得到输入二叉树的最大深度。
阅读全文