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

平衡二叉树（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);    
}    

 

 

 

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

补充：软件开发 , C语言 ,