平衡二叉树

Desicription

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
int GetHeight(TreeNode* root) {
if(root == nullptr) {
return 0;
}
int leftHeight = GetHeight(root->left);
int rightHeight = GetHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == nullptr) {
return true;
}
int leftHeight = GetHeight(pRoot->left);
int rightHeight = GetHeight(pRoot->right);
if(abs(leftHeight - rightHeight) > 1) {
return false;
}
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}
};