//平衡二叉树的概念：左右子树的深度相差不超过1
//判断一棵二叉树是不是平衡二叉树

#include <iostream>

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);
}
//*****************方法一****************************
////二叉树的深度
//    int TreeDepth(BinaryTreeNode* pRoot){
//        if(!pRoot)
//            return 0;
//    //    if(!pRoot->m_pLeft && !pRoot->m_pRight)//不需要
//    //        return 1;
//
//        //else{
//            int nLeft=TreeDepth(pRoot->m_pLeft);
//            int nRight=TreeDepth(pRoot->m_pRight);
//            return (nLeft>nRight)?(nLeft+1):(nRight+1);
//      //  }
//
//    }
//bool IsBalanced(BinaryTreeNode* pRoot){
//    if(pRoot==NULL)
//        return true;
//    int left=TreeDepth(pRoot->m_pLeft);
//    int right=TreeDepth(pRoot->m_pRight);
//    int diff= left-right;
//    if(diff>1 ||diff<-1)
//        return false;
//    return IsBalanced(pRoot->m_pLeft)&&IsBalanced(pRoot->m_pRight);
//}
//***********************方法二***********************88
//每个节点遍历一遍，就能判断二叉树是不是平衡的；采用后序遍历,遍历一个节点的时候，它的左右子树已经遍历过了。
//在遍历节点的时候记录 它的深度，就能一边遍历，一边判断每个节点是不是平衡的
bool IsBalancedCore(BinaryTreeNode* pRoot, int* pDepth){
    if(pRoot==NULL){
        *pDepth=0;
        return true;
    }
    int left,right;
    if(IsBalancedCore(pRoot->m_pLeft,&left)&& IsBalancedCore(pRoot->m_pRight,&right)){
        int diff=left-right;
        if(diff<=1 && diff>=-1){
            *pDepth=1+(left>right?left:right);
            return true;
        }
    }
    return false;
}
bool IsBalanced(BinaryTreeNode* pRoot){
    int depth=0;
    return IsBalancedCore(pRoot,&depth);
}
int main()
{
    BinaryTreeNode* Btree;
    int preorder[]={10,5,4,7,12};
    int inorder[]={4,5,7,10,12};
    Btree= Contrust(preorder,inorder,5);
    cout<<IsBalanced(Btree);
    return 0;
}