平衡二叉树是任意结点左右子树的深度相差不超过1的二叉树,例如下图所示的二叉树就是一棵平衡二叉树。
已知一棵二叉树采用二叉链表存储,结点结构为(left,data,right),root指向根节点。
编写算法判断该二叉树是否是一棵平衡二叉树。
算法题要求:
(1) 概要描述算法的思想;
(2) 在关键的地方给出简明的注释;
(3) 算法可使用C或ADL语言描述。
bool IsAVL(BianryTreeNode* pRoot, int& height) { if(pRoot == 0) return true; int leftHeight; bool leftResult = IsAVL(pRoot->left, leftHeight); int rightHeight; bool rightResult = IsAVL(pRoot->right, rightHeight); if(leftResult && rightResult && abs(leftHeight - rightHeight) <= 1) { height = max(leftHeight, rightHeight) + 1; return true; } else { height = max(leftHeight, rightHeight) + 1; return false; } }