首页 > 代码库 > Construct Binary Tree From Inorder and Preorder/Postorder Traversal

Construct Binary Tree From Inorder and Preorder/Postorder Traversal

map<int, int> mapIndex;void mapToIndex(int inorder[], int n){    for (int i = 0; i < n; i++)    {        mapIndex.insert(map<int, int>::value_type(inorder[i], i);    }}Node* buildInorderPreorder(int in[], int pre[], int n, int offset){    assert(n >= 0);    if (n == 0)        return NULL;    int rootVal = pre[0];    int i = mapIndex[rootVal] - offset;    Node* root = new Node(rootVal);    root->left = buildInorderPreorder(in, pre+1, i, offset);    root->right = buildInorderPreorder(in+i+1, pre+i+1, n-i-1, offset+i+1);    return root;}Node* buildInorderPostorder(int in[], int post[], int n, int offset){    assert(n >= 0);    if (n == 0)        return NULL;    int rootVal = post[n-1];    int i = mapIndex[rootVal] - offset;    Node* root = new Node(rootVal);    root->left = buildInorderPostorder(in, post, i, offset);    root->right = buildINorderPostorder(in+i+1, post+i, n-i-1, offset+i+1);    return root;}

 

Construct Binary Tree From Inorder and Preorder/Postorder Traversal