二叉树已知前序求中序
时间: 2023-12-20 08:28:19 浏览: 38
二叉树的前序遍历顺序是:根节点、左子树、右子树。中序遍历顺序是:左子树、根节点、右子树。因此,我们可以通过前序遍历和中序遍历的结果来构建一棵二叉树。
具体步骤如下:
1. 前序遍历的第一个节点是根节点,将其存储下来。
2. 在中序遍历中找到根节点的位置,根节点左边的所有节点都是左子树的节点,右边的所有节点都是右子树的节点。
3. 根据中序遍历中左子树的节点数量,可以在前序遍历中确定左子树的范围。
4. 递归处理左子树和右子树,直到所有节点都被处理完。
下面是代码实现:
```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)
idx = inorder.index(root_val)
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
```