请你以程序员的身份编写可以运行的二叉树的先序、中序、后序遍历的递归算法
时间: 2024-06-08 18:06:00 浏览: 123
好的,以下是使用 Python 语言编写的二叉树先序、中序、后序遍历的递归算法实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def preorderTraversal(root: TreeNode) -> List[int]:
"""
二叉树先序遍历递归算法
"""
if not root:
return []
res = []
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
def inorderTraversal(root: TreeNode) -> List[int]:
"""
二叉树中序遍历递归算法
"""
if not root:
return []
res = []
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
def postorderTraversal(root: TreeNode) -> List[int]:
"""
二叉树后序遍历递归算法
"""
if not root:
return []
res = []
res += postorderTraversal(root.left)
res += postorderTraversal(root.right)
res.append(root.val)
return res
```
以上代码中,首先定义了一个二叉树的节点类 `TreeNode`,包含节点值 `val`、左子节点 `left`、右子节点 `right` 三个属性。接着分别实现了二叉树的先序、中序、后序遍历递归算法,其中每个函数的输入参数是二叉树的根节点 `root`,输出参数是一个列表 `res`,表示遍历结果。当二叉树为空时,直接返回空列表;否则先遍历根节点,再递归遍历左子树和右子树,并将结果合并到 `res` 列表中。最后返回 `res` 列表即可。
注意,以上代码只是递归算法的实现,还有非递归算法的实现方式,可以使用栈来模拟遍历过程,我这里没有提供。
阅读全文