BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder){
// 前序遍历序列的第一个数字是根节点
int rootValue = startInorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
if (startPreorder == endPreorder)
{
if (startInorder == endInorder && *startPreorder == *startInorder)
{
return root;
}else{
throw std::exception("Invalid input.");
}
}
// 在中序遍历中找到根节点
int* rootInorder = startInorder;
// 如果当前指针对应的指不是根节点，那么指针向后移动一次
while(rootInorder <= endInorder && *rootInorder != rootValue){
++ rootInorder;
}
// 如果遍历完中序遍历的结果之后都没有找到和前序遍历结果相同的根节点
if (rootInorder == endInorder && *rootInorder != rootValue)
{
throw std::exception("Invalid input.");
}
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPreorder + leftLength;
if (leftLength > 0)
{
root->m_pLeft = ConstructCore(startPreorder + 1,leftPreorderEnd,startInorder,rootInorder - 1);
}
if (leftLength < endPreorder - startPreorder)
{
root->m_pRight = ConstructCore(leftPreorderEnd + 1,endPreorder,rootInorder + 1,endInorder);
}
return root;
}
转载请注明原文地址: https://www.6miu.com/read-70343.html
