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
已知二叉树的前序遍历这中序遍历,求二叉树,这个其实挺简单的,在前序遍历中取第一个元素,然后在中序遍历找到相应的元素,左边的为左子树,右边的为右子树,根据长度在前序遍历中找到相应左子树和右子树的前序遍历。然后就可以递归了。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
vector<int> leftpre;
vector<int> leftino;
vector<int> rightpre;
vector<int> rightino;
if(preorder.empty()||inorder.empty())
return NULL;
int root = preorder[0]; int left=0;int right=0;int tag=0;
for(int i=0;i<inorder.size();i++)
{
if(inorder[i]==root)
{
tag=1;
}
else if(tag==0)
{left++;leftino.push_back(inorder[i]);}
else
{right++;rightino.push_back(inorder[i]);}
}
for(int i=1;i<left+1;i++)
{
leftpre.push_back(preorder[i]);
}
for(int i=left+1;i<preorder.size();i++)
{
rightpre.push_back(preorder[i]);
}
TreeNode* tree = new TreeNode(root);
tree->left = buildTree(leftpre,leftino);
tree->right = buildTree(rightpre,rightino);
return tree;
}
};