用递归算法遍历二叉树
时间: 2023-09-09 13:08:15 浏览: 46
好的,遍历二叉树有三种方式,分别是前序遍历、中序遍历和后序遍历,下面是使用递归算法实现这三种遍历方式的代码:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 前序遍历
def preorderTraversal(root):
if root is None:
return []
res = []
res.append(root.val)
res.extend(preorderTraversal(root.left))
res.extend(preorderTraversal(root.right))
return res
# 中序遍历
def inorderTraversal(root):
if root is None:
return []
res = []
res.extend(inorderTraversal(root.left))
res.append(root.val)
res.extend(inorderTraversal(root.right))
return res
# 后序遍历
def postorderTraversal(root):
if root is None:
return []
res = []
res.extend(postorderTraversal(root.left))
res.extend(postorderTraversal(root.right))
res.append(root.val)
return res
```
以上代码中,我们首先定义了二叉树节点的类 TreeNode,然后分别实现了递归算法遍历二叉树的三种方式,即前序遍历、中序遍历和后序遍历。具体实现思路是,对于每个节点,先处理左子树,再处理右子树,最后处理根节点。我们通过递归调用函数来遍历整个二叉树,将遍历结果存到一个列表中,并返回该列表。