题解 | #判断是不是平衡二叉树#
判断是不是平衡二叉树
https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222
是平衡二叉树要满足两个条件：节点为空或者左右子树都为平衡二叉树（左右子树高度差不大于1）.那么设计递归边界的时候，就可以从这两方面考虑：只要节点为空，一定是平衡的；只要左右子树高度差大于1，一定不是平衡的。要写一个求高度的函数。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
*
* @param pRoot TreeNode类
* @return bool布尔型
*/
int height(struct TreeNode *pRoot){
if(!pRoot)return 0;
int left = height(pRoot -> left);
int right = height(pRoot -> right);
return left > right ? (left + 1) : (right + 1);
}
bool IsBalanced_Solution(struct TreeNode* pRoot ) {
if(!pRoot)return true;
int left = height(pRoot -> left);
int right = height(pRoot -> right);
if(abs(left - right) > 1)return false;
return IsBalanced_Solution(pRoot -> left) && IsBalanced_Solution(pRoot -> right);
}
查看19道真题和解析