实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过 1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
class Solution {
public:
bool isBalanced(TreeNode* root) {
bool ans = true;
check(root, ans);
return ans;
}
int check(TreeNode* root, bool& bal)
{
if(!root || !bal)
return 0;
int l = check(root->left, bal);
int r = check(root->right, bal);
if(abs(l-r)>1)
bal = false;
return max(l,r)+1;
}
};