algorithm - 平衡二叉树逻辑

Question

问题是确定给定的树(以 A 为根)是否平衡。 我写了这段代码。它在一个测试用例上失败了。 逻辑有什么问题？

int depth(TreeNode* root){
    if (root==NULL) return 0;
    else return max(depth(root->left),depth(root->right))+1;
}
int Solution::isBalanced(TreeNode* A) {
    if(A==NULL) return 1;
    if((abs(depth(A->left)-depth(A->right)))>1) return 0;
    else {
        isBalanced(A->left);
        isBalanced(A->right);
        return 1;
    }
}

Answer 1

您正在丢弃 else 子句中递归调用的结果。尝试这样的事情:

if((abs(depth(A->left) - depth(A->right))) <= 1 && isBalanced(A->left) && isBalanced(A->right)) {
    return 1;
}
else {
    return 0;
}