题目:solveNQueens
要求:
根据前序遍历和中序遍历树构造二叉树. 注意事项 你可以假设树中不存在相同数值的节点
样例:
给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:
2
/
\
1 3
算法要求:
无
解题思路:
看这里
算法如下:
vector<int> inorder;
vector<int> preorder;
TreeNode *build(
int startA,
int endA,
int startB,
int endB) {
if (startA > endA || startB > endB) {
return NULL;
}
TreeNode *root =
new TreeNode(inorder[startB]);
int headB = startB;
int headA = endA;
while (preorder[headA] != inorder[headB]) {
headA--;
}
root->left = build(startA, headA -
1, startB +
1, headA - startA + startB);
root->right = build(headA +
1, endA, headA - startA + startB +
1, endB);
return root;
}
TreeNode *buildTree(
vector<int> &inorder,
vector<int> &preorder) {
this->inorder = inorder;
this->preorder = preorder;
return build(
0, inorder.size() -
1,
0, preorder.size() -
1);
}
