首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。