使用递归方式计算二叉树的深度。提示:二叉树是根据先序遍历顺序建立起来的。
时间: 2023-04-18 16:04:20 浏览: 193
二叉树的深度可以使用递归的方式计算。具体而言,如果一个二叉树为空,那么它的深度为 0;否则,它的深度为左右子树深度的最大值加一。
以下是使用中文的代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
return max(maxDepth(root.left), maxDepth(root.right)) + 1
```
在上面的代码中,我们定义了一个名为 `maxDepth`二叉树是一种基于先序遍历顺序建立起来的树形结构。在计算二叉树的深度时,可以使用递归的方式来求解。
具体地,如果当前节点为空,则返回深度 0。否则,递归计算左子树的深度和右子树的深度,然后取它们的最大值,并加上 1,即为当前节点所在子树的深度。
以下是用中文表述的二叉树的深度计算的算法:
1. 如果当前节点为空,则返回深度 0。
2. 否则,递归计算左子树的深度和右子树的深度:
a. 计算左子树的深度:递归调用深度函数,传入左子节点为当前节点,得到左子树的深度 left_depth。
b. 计算右子树的深度:递归调用深度函数,传入右子节点为当前节点,得到右子树的深度 right_depth。
3. 取左子树深度和右子树深度的最大值,加上 1,即为当前节点所在子树的深度,返回该值。
这样,我们就可以使用递归的方式计算二叉树的深度了。
阅读全文