1、通过先序遍历找到根结点A，再通过A在中序遍历的位置找出左子树、右子树
2、在A的左子树中，转步骤1
3、在A的右子树中，转步骤1
/**
* 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:
int FindPos(vector<int>& inorder, int val)
{
int len = inorder.size();
for (int i=0; i<= len; ++i)
{
if (inorder[i] == val)
return i;
}
return -1;
}
TreeNode* PreInCreate(vector<int>& preorder, vector<int>& inorder)
{
TreeNode* root = NULL;
int len = preorder.size();
if (len > 0)
{
root = new TreeNode(preorder[0]);
int pos = FindPos(inorder, preorder[0]);
if (pos == -1)
return NULL;
vector<int> preLeft(preorder.begin() + 1, preorder.begin() + pos + 1);
vector<int> inLeft(inorder.begin(), inorder.begin() + pos);
root->left = PreInCreate(preLeft, inLeft);
vector<int> preRight(preorder.begin() + pos + 1, preorder.begin() + len);
vector<int> inRight(inorder.begin() + pos + 1, inorder.begin() + len);
root->right = PreInCreate(preRight, inRight);
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
int lenPre = preorder.size();
int lenIn = inorder.size();
if (lenPre <= 0 || lenIn <= 0 || lenPre != lenIn)
return NULL;
return PreInCreate(preorder, inorder);
};
//打印二叉树
//先序遍历
void PreOrder(TreeNode* root)
{
if (root == NULL)
return;
printf("data:%d\n", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历
void InOrder(TreeNode* root)
{
if (root == NULL)
return;
InOrder(root->left);
printf("data:%d\n", root->val);
InOrder(root->right);
}
};
