BST 递归的问题（在 C++ 中查找树的高度）

Question

int BST::getLength()
{
    int leftHeight = 0;
    int rightHeight = 0;

    // Empty case
    if (!prev && !dataInit)
        return 0;


    else
    {
        if (left)
        {
            leftHeight = left->getLength();

            std::cout << "leftHeight: " << leftHeight;
            std::cout << std::endl << std::endl;
        }
        if (right)
        {
            rightHeight = right->getLength();

            std::cout << "rightHeight: " << rightHeight;
            std::cout << std::endl << std::endl;
        }

        if (leftHeight > rightHeight)
            return leftHeight + 1;
        else
            return rightHeight + 1;
    }
}

这是从某个网站复制的功能。我一直试图在纸上写下这个函数来理解递归，但我似乎无法理解。具体来说，我不明白如果我们在加 1 之前递归调用它，leftHeight 和 rightHeight 是如何递增的。

如有任何帮助，我们将不胜感激。

Answer 1

我不完全确定这段代码其余部分的结构，但我会冒险猜测一下。如果我们开始考虑基本案例，它会有所帮助。对于二叉树，这将是叶节点。对于叶节点，其左右子节点的高度为零，包括叶节点在内的整棵树的高度为一。

那么我们可以退一步考虑二叉树中的一个一般节点：从这个节点开始的树的高度是max(leftSubTree, rightSubTree) + 1，其中+1是当前节点。

BST 递归的问题（在 C++ 中查找树的高度）

Troubles with BST recursion (finding height of a tree in C++)

c++

binary-search-tree