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

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。但是，如果存在子节点，则会对头节点进行计数。

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 ) );
}