# 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列`{1,2,4,7,3,5,6,8}`和中序遍历序列`{4,7,2,1,5,3,8,6}`，则重建二叉树并返回。

## 思路

* 前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历（根左右）
* 中序遍历：左子树中序遍历 + 根节点 + 右字数中序遍历（左根右）
* 后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点（左右根）

根据上面的规律：

* 前序遍历找到根结点`root`
* 找到`root`在中序遍历的位置 -> 左子树的长度和右子树的长度
* 截取左子树的中序遍历、右子树的中序遍历
* 截取左子树的前序遍历、右子树的前序遍历
* 递归重建二叉树

![](/files/-LyX0H3Wc4YBda8nuCDj)

```javascript
// pre 是前序数组 
// vin 是中序数组
function reConstruct(pre, vin) {
    if(pre.length === 0){
        return null;
    }
    if(pre.length === 1){
        return new TreeNode(pre[0]);
    }
    const value = pre[0];
    const index = vin.indexOf(value);
    const vinLeft = vin.slice(0,index);
    const vinRight = vin.slice(index+1);
    const preLeft = pre.slice(1,index+1);
    const preRight = pre.slice(index+1);
    const node = new TreeNode(value);
    node.left = reConstruct(preLeft, vinLeft);
    node.right = reConstruct(preRight, vinRight);
    return node;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mm.ricky.moe/algorithm/algorithm-and-data-structure/er-cha-shu-zhuan-ti/zhong-jian-er-cha-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.