//根据先序和中序构建二叉树，进一步的，判断一棵树是不是另一棵树的子树
#include  <iostream>\
#include<exception>
using namespace std;
struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

BinaryTreeNode* ContrustCore(int* startpreorder,int* endpreorder,int* startinorder,int* endinorder){
    //根据先序确定第一个数值确定根节点
   //BinaryTreeNode *root;
    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==*endpreorder)//z只有一个根节点
            return root;
        else
            throw std::exception();
    }
    //在中序找到根节点所在位置
    int*rootinoder=startinorder;
     while(rootinoder<=endinorder && *rootinoder!=rootValue)
        rootinoder++;
     if(rootinoder==endinorder && *rootinoder!=rootValue)//在中序中没有找到根节点
         throw exception();
     int leftLength=rootinoder-startinorder;
     int* leftPreorderEnd=startpreorder+leftLength;
     if(leftLength>0)//左子树的长度,构建左子树
     {
         root->m_pLeft=ContrustCore(startpreorder+1,leftPreorderEnd,startinorder,rootinoder-1);
     }
    if(leftLength<endpreorder-startpreorder)//存在右子树
        root->m_pRight=ContrustCore(leftPreorderEnd+1,endpreorder,rootinoder+1,endinorder);
    return root;
}
BinaryTreeNode* Contrust(int* preorder,int* inorder,int length){
        if(preorder==NULL||inorder==NULL||length<=0)
            return NULL;
        return ContrustCore(preorder,preorder+length-1,inorder,inorder+length-1);
}
void postorder(BinaryTreeNode* Btree){//后序遍历输出书的各个节点 
    if(Btree!=NULL){
        postorder(Btree->m_pLeft);
        postorder(Btree->m_pRight);
        cout<<Btree->m_nValue<<" ";
    }
}
//*************************************************
//判断根节点开始相同的树1是不是包含树2
bool DoesTree1haveTree2(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2){//完全匹配
    if(pRoot2==NULL)
        return true;
    if(pRoot1==NULL)
        return false;
    if(pRoot1->m_nValue!=pRoot2->m_nValue)
        return false;
    return DoesTree1haveTree2(pRoot1->m_pLeft,pRoot2->m_pLeft)&&DoesTree1haveTree2(pRoot1->m_pRight,pRoot2->m_pRight);
}
//判断树1是不是包含树2，不一定从根节点开始
bool HasSubtree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2){
    bool result=false;
    if(pRoot1!=NULL && pRoot2!=NULL){
        if(pRoot1->m_nValue==pRoot2->m_nValue)
            result=DoesTree1haveTree2(pRoot1,pRoot2);
        if(!result)
            result=HasSubtree(pRoot1->m_pLeft,pRoot2);
        if(!result)
            result=HasSubtree(pRoot1->m_pRight,pRoot2);

    }
     return result;
}

//****************************************************
//求一棵二叉树的镜像

void MirrorBinaryTree(BinaryTreeNode pNode){
if(pNode==NULL)
return;
if(pNode->m_pLeft==NULL && pNode->m_pRight==NULL)//叶子节点，没有左右子树
return;
BinaryTreeNode temp= pNode->m_pLeft;//交换非叶子节点
pNode->m_pLeft=pNode->m_pRight;
pNode->m_pRight=temp;
if(pNode->m_pLeft)
MirrorBinaryTree(pNode->m_pLeft);//递归交换非叶子节点的左右子树
if(pNode->m_pRight)
MirrorBinaryTree(pNode->m_pRight);

}
int main(){
BinaryTreeNode Btree1,Btree2;
int preorder1[]={10,8,9,2,4,7,7};
int inorder1[]={9,8,4,2,7,10,7};
int preorder2[]={8,9,2};
int inorder2[]={9,8,2};

        Btree1= Contrust(preorder1,inorder1,7);
        Btree2= Contrust(preorder2,inorder2,3);
        postorder(Btree1);
        cout<<endl;
    //    postorder(Btree2);
    //    cout<<endl<<"result:";
    //    cout<<HasSubtree(Btree2,Btree1);
        MirrorBinaryTree(Btree1);
        postorder(Btree1);
        return 0;

}