数据结构求二叉树深度
时间: 2023-10-17 16:36:08 浏览: 89
二叉树的深度可以通过递归或迭代的方式来求解。下面是递归的实现方式:
```python
class TreeNode:
def __init__(self, value):
self.val = value
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
```
在上述代码中,首先判断根节点是否为空,如果为空,则返回深度为0。如果不为空,则通过递归分别计算左子树和右子树的深度,然后取两者中较大的深度值,并加上当前节点的深度1,即可得到整棵树的深度。
你也可以使用迭代的方式来求解二叉树的深度,可以利用层次遍历的思想,通过队列来实现。具体代码如下:
```python
from collections import deque
def maxDepth(root):
if root is None:
return 0
queue = deque()
queue.append(root)
depth = 0
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth
```
以上是求解二叉树深度的两种常用方法,你可以根据具体情况选择递归或迭代的方式来实现。
阅读全文