原题如下
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:
代码语言：javascript复制 3
/
9 20
/
15 7思路
（1）前序序列的第一个元素一定是根节点； （2）中序序列中根节点左边为左子树的中序序列，右边为右子树的中序序列； （3）根据根节点在中序序列中的位置，又可在前序序列中得到左子树的前序序列和右子树的前序序列； （4）用相同的原理又能分别找出左右子树的根节点； （5）根节点的左子节点为左子树的根节点，右子节点为右子树的根节点； （6）再用相同的方法找出子节点的左右子节点；如此递归下去，直到最终序列为空。
代码
代码语言：javascript复制class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()) return NULL;
int size = preorder.size();
int root_value = preorder[0];
TreeNode* root = new TreeNode(root_value);
vector<int> pre_left, in_left, pre_right, in_right;
int i;
for(i = 0; i < size; i ){
int value = inorder[i];
if(value == root_value) break;
in_left.push_back(value);
pre_left.push_back(preorder[i 1]);
}
for(i ; i < size; i ){
in_right.push_back(inorder[i]);
pre_right.push_back(preorder[i]);
}
TreeNode* left = buildTree(pre_left, in_left);
TreeNode* right = buildTree(pre_right, in_right);
root->left = left;
root->right = right;
return root;
}
};后序和中序
思路类似，只不过根节点在postorder的末尾，代码如下：
代码语言：javascript复制class Solution {
public:
TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
if(postorder.empty()) return NULL;
int size = postorder.size();
int root_value = postorder[size - 1]; // 这里不同
TreeNode* root = new TreeNode(root_value);
vector<int> post_left, in_left, post_right, in_right;
int i;
for(i = 0; i < size; i ){
int value = inorder[i];
if(value == root_value) break;
in_left.push_back(value);
post_left.push_back(postorder[i]); // 这里不同
}
for(i ; i < size; i ){
in_right.push_back(inorder[i]);
post_right.push_back(postorder[i - 1]); // 这里不同
}
TreeNode* left = buildTree(post_left, in_left);
TreeNode* right = buildTree(post_right, in_right);
root->left = left;
root->right = right;
return root;
}
};
