根据先序遍历序列和中序遍历序列构建二叉树
时间: 2023-11-21 11:05:17 浏览: 78
构建二叉树的过程需要用到递归算法,具体流程如下:
1. 从先序遍历序列中取出第一个节点作为根节点,同时在中序遍历序列中找到该节点的位置,并将中序遍历序列分成左子树和右子树两个部分。
2. 对于左子树,递归地执行步骤1,构建出左子树;对于右子树,也递归地执行步骤1,构建出右子树。
3. 将左子树和右子树分别作为根节点的左右子树,构建出完整的二叉树。
下面是一个示例代码,用于构建二叉树:
```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 = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
```
其中,`preorder`和`inorder`分别代表先序遍历序列和中序遍历序列,函数返回构建出的二叉树的根节点。
阅读全文