【题解】牛牛的AVL

题意

给你一棵二叉树的中序遍历和层次遍历，让你判断这棵二叉树是不是平衡二叉树。

题解

首先我们需要通过中序遍历和层次遍历构建出一棵二叉树。那么需要怎么构建呢。首先若我们有了某棵子树的层次遍历序列，对于这棵子树来说肯定是这棵子树的根节点。那么我们获取到根节点后我们可以利用这个根节点通过中序遍历序列来获取这棵树左右子树的层次遍历序列。我们首先是知道这棵树左右子树在中序遍历序列中的区间范围的，然后我们遍历一开始的层序遍历序列，判断该节点是否在左子树中，若是加入左子树层次遍历序列，若不是我们让其加入右子树层次遍历序列，然后对左右子树重复上述过程就可以构建出一棵二叉树了。剩下的是如何判断是否是一棵平衡树了，根据平衡树的定义，任意节点的左右子树高度相差要小于2。所以我们写一个求树高度的函数，然后用dfs判断每个节点左右子树高度差就可以了。

复杂度

时间复杂度为
空间复杂度为

代码

struct BiTree
{
    int v;
    BiTree *lchild;
    BiTree *rchild;
};
BiTree *create(vector<int>level,vector<int>inorder,int inL,int inR)
{
    if(level.size()==0)
        return NULL;
    BiTree *T=new BiTree;
    T->v=level[0];
    int pos=-1;
    for(int i=inL;i<=inR;i++)
    {
        if(inorder[i]==level[0])
        {
            pos=i;
            break;
        }
    }
    vector<int>levelL;
    vector<int>levelR;
    for(int i=1;i<level.size();i++)
    {
        int isL=0;
        for(int j=inL;j<pos;j++)
        {
            if(level[i]==inorder[j])
            {
                isL=1;
                break;
            }
        }
        if(isL)
        {
            levelL.push_back(level[i]);
        }
        else
        {
            levelR.push_back(level[i]);
        }
    }
    T->lchild=create(levelL,inorder,inL,pos-1);
    T->rchild=create(levelR,inorder,pos+1,inR);
    return T;
}
int height(BiTree *T)
{
    if(T==NULL)
        return 0;
    int L=height(T->lchild)+1;
    int R=height(T->rchild)+1;
    return max(L,R);
}
bool judge(BiTree *T)
{
    int L=height(T->lchild);
    int R=height(T->rchild);
    if(abs(L-R)>1)
        return 0;
    if(T->lchild!=NULL)
    judge(T->lchild);
    if(T->rchild!=NULL)
    judge(T->rchild);
    return 1;
}
class Solution {
public:
    /**
     * 
     * @param inorder int整型vector 中序遍历序列
     * @param level int整型vector 层次遍历序列
     * @return bool布尔型
     */
    bool isBalanceTree(vector<int>& inorder, vector<int>& level) {
        // write code here
        BiTree *T=create(level,inorder,0,inorder.size()-1);
        return judge(T);
    }
};