c++ - 计算返回 -1 混淆的 BST 的高度？

Question

为什么我们在没有节点或 nullptr 时返回 -1？我无法弄清楚它的逻辑以及它如何用 +1 取消

int height( BinaryNode * node ) const {
    if ( node == nullptr ) 
        return -1;

    else 
        return 1 + std::max( height( node->left ), height( node->right ) );
    }

Answer 1

函数有逻辑错误。

如果头节点不等于 nullptr 但没有子节点，则函数返回 0。但是，如果有 child ，则头节点会被反击。

    return 1 + std::max( height( node->left ), height( node->right ) );
          ^^^

像这样重写函数就可以了

int height( BinaryNode * node ) const 
{
    return node == nullptr ? 0 : 1 + std::max( height( node->left ), height( node->right ) );
}

或者

int height( const BinaryNode * node ) const 
{
    return node == nullptr ? 0 : 1 + std::max( height( node->left ), height( node->right ) );
}

因为树没有被这个函数改变。

由于树的高度不能为负，因此最好将返回类型设置为 unsigned int 或 size_t。例如

size_t height( const BinaryNode * node ) const 
{
    return node == nullptr ? 0 : 1 + std::max( height( node->left ), height( node->right ) );
}