设计一个算法(函数)来计算二叉树的深度。在main程序中测试。若将该递归算法转换成非递归算法,可采用什么方法?为什么?
时间: 2024-02-15 21:04:32 浏览: 23
可以使用递归算法来计算二叉树的深度。具体实现方法如下:
```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
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
```
其中,如果当前节点为空,则返回0;否则,分别递归计算左子树和右子树的深度,并取其中较大值加1作为当前节点的深度。
如果将递归算法转换成非递归算法,可以使用栈来实现。具体实现方法如下:
```python
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
stack = [(1, root)]
depth = 0
while stack:
cur_depth, node = stack.pop()
if node:
depth = max(depth, cur_depth)
stack.append((cur_depth+1, node.left))
stack.append((cur_depth+1, node.right))
return depth
```
其中,栈中存放的是二元组,表示节点的深度和节点本身。每次弹出栈顶元素,如果节点不为空,则更新当前深度并计算最大深度,然后将左右子节点压入栈中,并将深度加1。最后返回最大深度即可。
这种方法叫做DFS(深度优先搜索),因为它本质上是一种搜索算法,而且是从根节点开始向下递归,直到叶子节点,然后回溯到前一个节点,再向下搜索其他分支。这种算法的好处是代码简单易懂,而且空间复杂度较低,时间复杂度为O(n),其中n为二叉树的节点数。