题目描述：
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
解题思路:
时间复杂度: $O(n^2)$,空间复杂度：$O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
// 递归的判断是否是平衡二叉树
bool IsBalanced_Solution(TreeNode* pRoot) {
// 如果初始节点是NULL，直接返回true
if(pRoot == NULL ) return true;
int left = 0, right = 0;
// 递归计算左子树的深度
left = dep_tree(pRoot->left);
// 递归的计算右子树的深度
right = dep_tree(pRoot->right);
// 判断两个深度的差值是否大于1，如果大于1，返回false
if(abs(left - right) > 1)
return false;
// 否则，递归的计算左子树和右子树
else
return IsBalanced_Solution(pRoot -> left) && IsBalanced_Solution(pRoot -> right);
}
// 计算树的深度
int dep_tree(TreeNode* pRoot)
{
if(!pRoot) return 0;
return max(dep_tree(pRoot->left),dep_tree(pRoot->right))+1;
}
};
|