leetcode 110.平衡二叉树
在第104题中,maxdepth函数实际上遍历了二叉树中每个节点的左右子树的高度,对其稍加修改,当检查到两子树高度差大于1时返回一个特定异常值即可。
bool isBalanced(TreeNode *root)
{
if (root == nullptr)
{
return true;
}
int a = maxDepth_extern(root);
if (a == -1)
{
return false;
}
return true;
}
int maxDepth_extern(TreeNode *root)
{
if (root == nullptr)
{
return 0;
}
int left_depth = 1 + maxDepth_extern(root->left);
int right_depth = 1 + maxDepth_extern(root->right);
if (left_depth == 0 || right_depth == 0)
{
return -1;
}
if (abs(right_depth - left_depth) >= 2)
{
return -1;
}
return left_depth >= right_depth ? left_depth : right_depth;
}