1、重复遍历结点

2、遍历一遍结点

# 代码：

```struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
};

int TreeDepth(TreeNode* pRoot){
if(pRoot==NULL)
return 0;
int left=TreeDepth(pRoot->left);
int right=TreeDepth(pRoot->right);
return left>right?(left+1):(right+1);
}

bool IsBalanced(TreeNode* pRoot){
if(pRoot==NULL)
return true;
int left=TreeDepth(pRoot->left);
int right=TreeDepth(pRoot->right);
int diff=left-right;
if(diff>1 || diff<-1)
return false;
return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}
```

```bool IsBalanced_1(TreeNode* pRoot,int& depth){
if(pRoot==NULL){
depth=0;
return true;
}
int left,right;
int diff;
if(IsBalanced_1(pRoot->left,left) && IsBalanced_1(pRoot->right,right)){
diff=left-right;
if(diff<=1 || diff>=-1){
depth=left>right?left+1:right+1;
return true;
}
}
return false;
}

bool IsBalancedTree(TreeNode* pRoot){
int depth=0;
return IsBalanced_1(pRoot,depth);
}```

# 在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/8b3b95850edb4115918ecebdf1b4d222?rp=2

AC代码：

```class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL)
return true;
int left=TreeDepth(pRoot->left);
int right=TreeDepth(pRoot->right);
int diff=left-right;
if(diff>1 || diff<-1)
return false;
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}

int TreeDepth(TreeNode* pRoot){
if(pRoot==NULL)
return 0;
int left=TreeDepth(pRoot->left);
int right=TreeDepth(pRoot->right);
return left>right?(left+1):(right+1);
}
};
```

```class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
int depth=0;
return IsBalanced(pRoot,depth);
}

bool IsBalanced(TreeNode* pRoot,int& depth){
if(pRoot==NULL){
depth=0;
return true;
}
int left,right,diff;
if(IsBalanced(pRoot->left,left) && IsBalanced(pRoot->right,right)){
diff=left-right;
if(diff<=1 && diff>=-1){
depth=left>right?left+1:right+1;
return true;
}
}
return false;
}
};```
原文作者：AndyJee
原文地址: https://www.cnblogs.com/AndyJee/p/4678757.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。