老公被带老鼠血的针刺了# Biology - 生物学
s*y
1 楼
Construct Binary Tree From Inorder and Preorder/Postorder Traversal
const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
for (int i = 0; i < n; i++) {
assert(0 <= inorder[i] && inorder[i] <= MAX-1);
mapIndex[inorder[i]] = i;
}
}
// precondition: mapToIndices must be called before entry
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; // the divider's index
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;
}
如果有2个node的元素值一样，这个用hash保存mapIndex是不是就不行了，一定要每次
慢慢找，或者用chaining建立hash？
还有buildInorderPreorder 这个函数传进去的参数int in[]似乎在建立了mapIndex就
没有用了，根本不需要传这个进去。
const int MAX = 256;
// a fast lookup for inorder's element -> index
// binary tree's element must be in the range of [0, MAX-1]
int mapIndex[MAX];
void mapToIndices(int inorder[], int n) {
for (int i = 0; i < n; i++) {
assert(0 <= inorder[i] && inorder[i] <= MAX-1);
mapIndex[inorder[i]] = i;
}
}
// precondition: mapToIndices must be called before entry
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; // the divider's index
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;
}
如果有2个node的元素值一样，这个用hash保存mapIndex是不是就不行了，一定要每次
慢慢找，或者用chaining建立hash？
还有buildInorderPreorder 这个函数传进去的参数int in[]似乎在建立了mapIndex就
没有用了，根本不需要传这个进去。
