题目描述
blablabla
算法1
(暴力枚举) $O(n)$
将求深度的代码稍作修改,不重复求深度。
时间复杂度分析:因为只遍历结点一次,所以最坏情形为O(n)
C++ 代码
class Solution {
public:
bool isBalanced(TreeNode* root) {
/*
unit test
root is nil
root not nil, left is nil, right is nil
root not nil, left not nil, right nil.
*/
int height=dfs(root);
if(height>=0) return true;
else return false;
}
// 当非平衡时,return -1; 平衡时,return high;
// 首先判断左子树平衡与否,再判断右子树平衡与否,在判断整棵树平衡与否;
int dfs(TreeNode *root){
if(!root) return 0;
int left=dfs(root->left);
if(left<0) return -1;
int right=dfs(root->right);
if(right<0) return -1;
if(abs(left-right)>1) return -1;
return max(left,right)+1;
}
};
求两次深度结果炸了的大冤种在此