二叉树

重建二叉树

输入二叉树的前序遍历和中序遍历，重建二叉树

`

#include

#include

using namespace std;

struct TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* dfs(vector& preorder, int preleft, int preright, vector& inorder, int inleft, int inright){

if(preleft>preright || inleft>inright)
    return NULL;

TreeNode* node=new TreeNode(preorder[preleft]);

int i=0;

for(i=inleft; i<=inright; ++i){
    if(inorder[i]==node->val)
        break;
}

node->left=dfs(preorder, preleft+1, preleft+i-inleft, inorder, inleft, i-1);
node->right=dfs(preorder, preleft+i-inleft+1, preright, inorder, i+1, inright);

return node;

}

TreeNode* rebuild(vector& preorder, vector& inorder){

int presize=preorder.size();
int insize=inorder.size();

TreeNode* res=NULL;
if(presize==0 || presize!=insize)
    return NULL;

res=dfs(preorder, 0, presize-1, inorder, 0, insize-1);

return res;

}

void inorderTree(TreeNode* tree, vector& res){
if(!tree)
return;

inorderTree(tree->left, res);
res.push_back(tree->val);
inorderTree(tree->right, res);

}