# 2.解法一

```//求二叉树的高度
int treeDepth(BinaryTreeNode* root){
if(root==NULL){
return 0;
}
int nLeft=treeDepth(root->m_pLeft);
int nRight=treeDepth(root->m_pRight);
return nLeft>nRight?nLeft+1:nRight+1;
}

bool isBalanced(BinaryTreeNode* root){
if(root==NULL)
return true;//空树是平衡二叉树
int left= treeDepth(root->m_pLeft);
int right= treeDepth(root->m_pRight);
int diff=left-right;
if(diff>1||diff<-1)
return false;
return isBalanced(root->m_pLeft)&&isBalanced(root->m_pRight);
}```

# 2.解法二

```bool IsBalanced(BinaryTreeNode* pRoot, int* depth){
if(pRoot== NULL){
*depth = 0;
return true;
}

int nLeftDepth,nRightDepth;
bool bLeft= IsBalanced(pRoot->m_pLeft, &nLeftDepth);
bool bRight = IsBalanced(pRoot->m_pRight, &nRightDepth);

if (bLeft && bRight){
int diff = nRightDepth-nLeftDepth;
if (diff<=1 && diff>=-1) //左右字树高度差绝对值不超过1
{
*depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);
return true;
}
}
return false;
}

bool IsBalanced(BinaryTreeNode* pRoot)
{
int depth = 0;

return IsBalanced(pRoot, &depth);
}  ```

# 参考文献

[1]http://blog.csdn.net/k346k346/article/details/51076268. [2]剑指Offer.何海涛.电子工业出版社.

472 篇文章40 人订阅

0 条评论

## 相关文章

12720

13420

12120

9520

22550

842110

### Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

29450

28550

39690

19340