《剑指Offer》面试题6.
思想：递归
代码：
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder);
BinaryTreeNode* Construct(int* preorder,int* inorder,int length)
{
if(preorder== NULL|| inorder== NULL|| length<=0)
return NULL;
returnConstructCore(preorder, preorder+ length-1,
inorder,inorder +length-1);
}
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder)
{
// 前序遍历序列的第一个数字是根结点的值
int rootValue= startPreorder[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;
}
// ====================测试代码====================
void Test(char* testName,int* preorder,int* inorder,int length)
{
if(testName!= NULL)
printf("%s begins:\n",testName);
printf("The preorder sequence is: ");
for(int i=0; i< length; ++ i)
printf("%d ",preorder[i]);
printf("\n");
printf("The inorder sequence is: ");
for(int i=0; i< length; ++ i)
printf("%d ",inorder[i]);
printf("\n");
try
{
BinaryTreeNode* root= Construct(preorder,inorder, length);
PrintTree(root);
DestroyTree(root);
}
catch(std::exception& exception)
{
printf("Invalid Input.\n");
}
}
思想：通过根节点将序列划分为左子树序列和右子树序列，他们必须满足的条件是：左子树序列中的所有值小于根节点，右子树中所有值大于根节点，然后递归判断左子树序列和右子树序列。
代码：
// BST：BinarySearch Tree，二叉搜索树
bool VerifySquenceOfBST(int sequence[], int length )
{
if (sequence == NULL || length <=0)
returnfalse ;
int root = sequence[ length -1];
//在二叉搜索树中左子树的结点小于根结点
int i =0;
for(; i < length -1;++ i )
{
if ( sequence [ i ]> root )
break ;
}
//在二叉搜索树中右子树的结点大于根结点
int j = i ;
for(; j < length -1;++ j )
{
if ( sequence [ j ]< root )
returnfalse ;
}
//判断左子树是不是二叉搜索树
bool left =true ;
if ( i >0)
left = VerifySquenceOfBST( sequence , i );
//判断右子树是不是二叉搜索树
bool right =true ;
if ( i < length -1)
right = VerifySquenceOfBST( sequence + i , length - i -1);
return (left && right ); }