# LeetCode105. Construct Binary Tree from Preorder and Inorder Traversal（二叉树 / 思维）

## LeetCode105. Construct Binary Tree from Preorder and Inorder Traversal（二叉树 / 思维）

• Medium
• Accepted：203,795
• Submissions：513,642

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

### 链接

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

### 题解

3 [9] [20, 15, 7] // 根 左 右
[9] 3 [15, 20, 7] // 左 右 根

20 [15] [7] // 根 左 右
[15] 20 [7] // 左 右 根

[3] 9 20 15 7 // 根 左 右
9 15 7 20 [3] // 左 右 根

[9] 20 15 7
[9] 15 7 20

### 代码

Time SubmittedStatusRuntimeMemoryLanguage
4 hours agoAccepted28 ms16.7 MBcpp
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
return solve(preorder, inorder, 0, 0, n);
}

private:
TreeNode* solve(vector<int>& preorder, vector<int>& inorder, int preStart, int inStart, int size)
{
if (size <= 0)
return NULL;
int root = preorder[preStart], pos = 0; // pos代表根节点在后序遍历中位置，默认为0
for (int i = inStart; i < inStart + size; ++i)
{
if (inorder[i] == root)
{
pos = i;
break;
}
}
TreeNode* bt = new TreeNode(root);
pos = (pos == 0) ? pos : pos - inStart; // 之前是从inStart的所以要减去
bt->left = solve(preorder, inorder, preStart + 1, inStart, pos);
bt->right = solve(preorder, inorder, preStart + pos + 1, inStart + pos + 1,  size - pos - 1);
return bt;
}
};

The end.
2019年3月13日 星期三