[互联网面试笔试汇总C/C++-16] 判断一棵二叉树是否是平衡二叉树 - c语言编程

首先，看一下平衡二叉树的定义：

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路：利用递归的思想

代码：

int DepthTree(BSTreeNode *pbs)    
{    
    if (pbs==NULL)    
        return 0;    
    else    
    {    
        int leftLength=DepthTree(pbs->left);    
        int rigthLength=DepthTree(pbs->right);    
        return 1+(leftLength>rigthLength   leftLength:rigthLength);    
    }    
}    
    
bool isBalanceTree(BSTreeNode *pbs)    
{    
    if (pbs==NULL)    
    {    
        return true;    
    }    
        
    int depthLeft=DepthTree(pbs->




left);    
    int depthRight=DepthTree(pbs->right);    
        
    if (abs(depthLeft-depthRight)>1)     
         return false;    
    else    
        return isBalanceTree(pbs->left) && isBalanceTree(pbs->right);    
}

改进：这样实际上是有很多重复计算的，如果想进一步提高效率的话可以考虑保存递归过程中的结果。