# 105.Construct Binary Tree from Preorder and Inorder Traversal

**105 Construct Binary Tree from Preorder and Inorder Traversal**

难度:Medium

> 根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = \[3,9,20,15,7] 中序遍历 inorder = \[9,3,15,20,7] 返回如下的二叉树：

```
    3
   / \
  9  20
    /  \
   15   7
```

先序遍历：根左右， 中序遍历：左根右。 先序遍历的第一个就是根节点，然后中序遍历中找到根节点，左边是左子树，右边是右子树，以此遍历。

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
int rs=0;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int sis, int eis) {
    if(rs>preorder.size()-1) return nullptr;
    TreeNode* root= new TreeNode(preorder[rs]);
    TreeNode* cur=root;
        int nis;
        for(int i=sis;i<eis;i++)
        if(inorder[i]==preorder[rs]) {nis=i; break;}

        if(nis>sis) {rs++; root->left = buildTree(preorder,inorder,sis,nis-1);}
        if(nis<eis) { rs++;root->right = buildTree(preorder, inorder,  nis+1,eis);}
        return root;
}

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || inorder.empty()) return nullptr;
         return buildTree(preorder, inorder,  0,inorder.size()-1);
    }
};
```

> 执行用时 :44 ms, 在所有 C++ 提交中击败了41.72%的用户\
> 内存消耗 :17.4 MB, 在所有 C++ 提交中击败了45.45%的用户


---

# 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://dfine.gitbook.io/leetcode/105.construct_binary_tree_from_preorder_and_inorder_traversal.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.