判断一个二叉树是不是是平衡二叉树 Cracking the coding interview 4.1

判断一个二叉树是否是平衡二叉树 Cracking the coding interview 4.1

平衡二叉树的定义是：任意节点的左子树的高度和右子树的高度之差小于等于1.

那么一个二叉树是平衡二叉树 当且仅当 (1,左子树是平衡二叉树, 2. 右子树是平衡二叉树; 3, 左右子树的高度之差小于等于1).

所以用递归的方法判断的话，递归函数就需要返回两个信息：是否平衡，树高度. 代码如下。

bool IsBalance(Node *pRoot, int & nDeepth){if (pRoot == NULL){nDeepth = 0;return true;}int deepRight;int deepLeft;if (!IsBalance(pRoot->pRight, deepRight) ||!IsBalance(pRoot->pLeft, deepLeft))return false;nDeepth = 1 + fmax(deepRight, deepLeft);return abs(deepRight - deepLeft)<=1;}