通过二叉树的先中序遍列画二叉树
时间: 2023-12-01 13:41:06 浏览: 23
通过二叉树的先序遍历和中序遍历可以画出一棵二叉树,具体步骤如下:
1.先序遍历的第一个节点一定是根节点,找到根节点在中序遍历中的位置,可以将中序遍历分为左子树和右子树两部分。
2.根据左子树和右子树的节点数量,可以在先序遍历中找到左子树和右子树的节点范围。
3.对于左子树和右子树,分别递归执行步骤1和步骤2,直到叶子节点。
4.重复执行步骤1到步骤3,直到构建出整棵二叉树。
下面是一个Python实现的例子:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = buildTree(preorder, inorder)
```