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

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