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

[互联网面试笔试汇总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);  
}  

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