给出二叉树的前序和中序,如何求二叉树
时间: 2023-06-17 09:07:04 浏览: 89
可以使用递归的方法来构建二叉树。前序遍历的第一个节点为根节点,在中序遍历中找到根节点,根节点左侧的部分为左子树,根节点右侧的部分为右子树。然后递归地构建左子树和右子树。
具体步骤如下:
1. 在前序遍历中找到根节点,创建一个节点,并将其值设置为根节点的值。
2. 在中序遍历中找到根节点的位置,以该位置为界限,将中序遍历分为左右两部分。
3. 递归地构建左子树和右子树,分别使用左子树的中序遍历和前序遍历,以及右子树的中序遍历和前序遍历进行递归构建。
4. 将左子树和右子树分别设置为根节点的左子树和右子树。
下面是一个Python实现的例子:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(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 = buildTree(preorder[1:index+1], inorder[:index])
root.right = buildTree(preorder[index+1:], inorder[index+1:])
return root
```
使用该函数可以构建一个二叉树,例如:
```python
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
```
构建出的二叉树如下所示:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
阅读全文