文章目录
题目描述法一：自顶向下的递归 O(n^2)法二：自底向上的递归 O(n)总结
//经典leetcode简单题。。。
题目描述
法一：自顶向下的递归 O(n^2)
class Solution {
public:
int height(TreeNode
*root
){
if(root
== NULL) return 0;
return max(height(root
->left
), height(root
->right
)) + 1;
}
bool isBalanced(TreeNode
* root
) {
if(root
== NULL) return true;
return abs(height(root
->left
) - height(root
->right
) <= 1) && isBalanced(root
->left
) && isBalanced(root
->right
);
}
};
简写
class Solution {
public:
bool isBalanced(TreeNode
* root
) {
return !root
? true : abs(depth(root
->left
) - depth(root
->right
)) <= 1 && isBalanced(root
->left
) && isBalanced(root
->right
);
}
int depth(TreeNode
* cur
) {
return !cur
? 0 : max(depth(cur
->left
), depth(cur
->right
)) + 1;
}
};
法二：自底向上的递归 O(n)
class Solution {
public:
int rightOrNot(TreeNode
*root
){
if(root
== NULL) return 0;
int leftHeight
= rightOrNot(root
->left
);
int rightHeight
=rightOrNot(root
->right
);
if(leftHeight
== -1 || rightHeight
== -1 || abs(leftHeight
- rightHeight
) > 1) return -1;
else return max(leftHeight
, rightHeight
) + 1;
}
bool isBalanced(TreeNode
* root
) {
return rightOrNot(root
) >= 0;
}
};
总结
树的递归相关题，盯着他的子树做文章
