计算返回 -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 但没有子节点函数 returns 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 ) );
}

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

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

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

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

Calculating height of a BST returning -1 confusion?

c++

algorithm

binary-tree

binary-search-tree