教我二叉树的先序中序后序遍历
时间: 2023-06-21 21:04:50 浏览: 85
二叉树的遍历方式有三种,分别是先序遍历、中序遍历和后序遍历。其中,先序遍历先访问根节点,然后访问左子树,最后访问右子树;中序遍历先访问左子树,然后访问根节点,最后访问右子树;后序遍历先访问左子树,然后访问右子树,最后访问根节点。下面是二叉树的三种遍历方式的代码实现:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 先序遍历
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
# 中序遍历
def inorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = inorderTraversal(root.left)
res += [root.val]
res += inorderTraversal(root.right)
return res
# 后序遍历
def postorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = postorderTraversal(root.left)
res += postorderTraversal(root.right)
res += [root.val]
return res
```
以上代码中,我们定义了一个二叉树节点类 `TreeNode`,包含节点值 `val`,左子树 `left` 和右子树 `right`。在三种遍历方式中,我们都使用了递归的方式来遍历整个二叉树。在每次递归时,我们先判断当前节点是否为空,如果为空则返回空列表。否则,我们按照先访问根节点、左子树、右子树的顺序(先序遍历)、先访问左子树、根节点、右子树的顺序(中序遍历)、先访问左子树、右子树、根节点的顺序(后序遍历)来递归遍历整个二叉树,并将遍历结果保存在一个列表中返回。