递归构建二叉树前中后遍历
时间: 2023-10-14 22:19:42 浏览: 34
递归构建二叉树:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
index = inorder.index(root_val)
root.left = build_tree(preorder[1:index+1], inorder[:index])
root.right = build_tree(preorder[index+1:], inorder[index+1:])
return root
```
其中,preorder 表示前序遍历序列,inorder 表示中序遍历序列。
前序遍历:根节点 -> 左子树 -> 右子树
中序遍历:左子树 -> 根节点 -> 右子树
后序遍历:左子树 -> 右子树 -> 根节点
前序遍历的第一个元素即为当前树的根节点,然后找到它在中序遍历中的位置,这样就可以确定左子树和右子树的大小,并进行递归构建二叉树。
前序遍历:
```python
def pre_order(root):
if not root:
return
print(root.val, end=' ')
pre_order(root.left)
pre_order(root.right)
```
中序遍历:
```python
def in_order(root):
if not root:
return
in_order(root.left)
print(root.val, end=' ')
in_order(root.right)
```
后序遍历:
```python
def post_order(root):
if not root:
return
post_order(root.left)
post_order(root.right)
print(root.val, end=' ')
```
示例:
```python
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = build_tree(preorder, inorder)
pre_order(root) # 1 2 4 5 3 6 7
print()
in_order(root) # 4 2 5 1 6 3 7
print()
post_order(root) # 4 5 2 6 7 3 1
```
输出结果为:
```
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
```