共计 1057 个字符，预计需要花费 3 分钟才能阅读完成。
题目
leetcode 105，https://leetcode.com/problems…
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
思路
前序遍历的第一个节点就是 root，用这个 root 可以把中序遍历的列表正好分为两段，分别是左右子树。左右子树的 size，正好是前序有序的两段。因此，可以根据前序第一个节点，划分出两个前序 + 中序的序列，递归生成子树。再将子树连接到 root 上。
代码
/**
* 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) {
int size = preorder.size();
if (size == 0) {return NULL;}
int p_idx = 0;
int root_val = preorder[p_idx++];
TreeNode* root = new TreeNode(root_val);
vector<int> p1,p2;
vector<int> i1,i2;
bool in_left = true;
for (int i = 0; i < size; i++) {
if (inorder[i] == root_val) {
in_left = false;
continue;
}
if (in_left) {
i1.push_back(inorder[i]);
p1.push_back(preorder[p_idx++]);
} else {
i2.push_back(inorder[i]);
p2.push_back(preorder[p_idx++]);
}
}
root->left = buildTree(p1, i1);
root->right = buildTree(p2, i2);
return root;
}
};
