二叉树先序中序后序递归遍历
时间: 2023-11-20 09:56:20 浏览: 106
二叉树的先序中序后序遍历
二叉树的遍历方式有三种:前序遍历、中序遍历和后序遍历。递归是实现这三种遍历方式的常用方法。
1. 前序遍历:先访问根节点,再访问左子树,最后访问右子树。
```python
def preorderTraversal(root):
if not root:
return []
res = []
res.append(root.val)
res += self.preorderTraversal(root.left)
res += self.preorderTraversal(root.right)
return res
```
2. 中序遍历:先访问左子树,再访问根节点,最后访问右子树。
```python
def inorderTraversal(root):
if not root:
return []
res = []
res += self.inorderTraversal(root.left)
res.append(root.val)
res += self.inorderTraversal(root.right)
return res
```
3. 后序遍历:先访问左子树,再访问右子树,最后访问根节点。
```python
def postorderTraversal(root):
if not root:
return []
res = []
res += self.postorderTraversal(root.left)
res += self.postorderTraversal(root.right)
res.append(root.val)
return res
```
阅读全文