🥧递归
和一般递归不同的地方在于，不能返回平衡因子，必须返回高度，并且设置一个-1的特殊值来作为失败的结果（用来代替bool）。
这里不能返回bool类型，因为bool无法传递高度值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool isBalanced(TreeNode* root) {
return helper(root) != -1;
}
int helper(TreeNode* h) {
if(!h)
return 0;
int lf = helper(h->left),
rf = helper(h->right);
if(lf == -1 || rf == -1)
return -1;
return abs(rf - lf) <= 1 ? max(lf, rf) + 1: -1;
}
};
|
Accepted
227/227 cases passed (20 ms)
Your runtime beats 44.47 % of cpp submissions
Your memory usage beats 9.13 % of cpp submissions (17.6 MB)
