# 105. Construct Binary Tree from Preorder and Inorder Traversal

## problem description

Given preorder and inorder traversal of a tree, construct the binary tree.

**Note:**\
You may assume that duplicates do not exist in the tree.

For example, given

```
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
```

Return the following binary tree:

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

## algorithm thought

前序遍历和中序遍历转二叉树，首先利用前序遍历第一个值就是当前根节点的性质。找到根节点，只有去中序遍历中找到根节点对应的位置，位置左边就是左子树右边是右子树。然后对于左右子树，得到他们的大小，去前序遍历中找到他们对应的位置。然后对于左右子树，递归解决。

## code

```cpp
/**
 * 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 {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,inorder,0,preorder.size(),0,inorder.size());
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int prelow,int prehigh,int inlow,int inhigh){
        if(prelow==prehigh)
            return NULL; 
        TreeNode* root=new TreeNode(preorder[prelow]);
        int inroot;
        for(int i=inlow;i<inhigh;i++){
            if(inorder[i]==preorder[prelow]){
                inroot=i;
                break;
            }
        }
        int leftsize=inroot-inlow;
        int rightsize=inorder.size()-inroot-1;
        root->left=build(preorder,inorder,prelow+1,prelow+1+leftsize,inlow,inroot);
        root->right=build(preorder,inorder,prelow+1+leftsize,prehigh,inroot+1,inhigh);
        return root;
    }
};
```

## algorithm analysis

每次在中序遍历中找到根节点的位置，一般情况下需要O(n)时间。那总时间可以表达为T(n)=2T(n/2)+O(n)，这个表达式用主定理分析可知为T(n)=O(nlgn)


---

# 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://kongchengzhuge.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.