计算BST高度的递归过程是如何工作的

Question

我有一个二叉树，高度是根据以下代码计算的-

public int height(Node root) {
    if (root == null)
        return -1;
    Node focusNode = root; 
    int leftHeight = focusNode.leftChild != null ? height( focusNode.leftChild) : 0;
    int rightHeight = focusNode.rightChild != null ? height( focusNode.rightChild) : 0;
    return 1 + Math.max(leftHeight, rightHeight);
}

如果根节点的左或右子节点不为空，则再次调用相同的height方法并继续递归。否则，返回0。我很难理解如何计算增加(比如，像c +=1，你看到它为每个循环增加1)。

谁能给我详细解释一下吗?

Answer 1

此处计数增加:

return 1 + Math.max(leftHeight, rightHeight);

，因为每次递归调用返回1 +前两次递归调用结果的高者。

Answer 2

让我们使用一个简单的示例树:

  r
 / 
A   

要确定它的高度，我们从r开始。为了计算r下子树的高度，我们首先计算左子树的高度，然后计算右子树的高度。然后我们选择较高的子树并将1添加到它的高度(即我们将r(1)的高度添加到较高的子树)。

int leftHeight = focusNode.leftChild != null ? height( focusNode.leftChild) : 0;
// if the left subtree exists, calculate its height.
// the height is zero if there is no left subtree

现在，左子树的高度是根在A的树的高度(暂时忽略r的存在)。递归表示，以A为根的树的高度还是它的最高子树的高度加上1。A的左子树是NULL，所以它的高度是0。A的右子树也是NULL，所以它的高度也是0。

因此以A为根的子树的高度为max(0, 0) + 1，这也是我们返回到r的数字;r的左子树的高度为1。

int rightHeight = focusNode.rightChild != null ? height( focusNode.rightChild) : 0;
// if the right subtree exists, calculate its height.
// the height is zero if there is no right subtree

现在我们向右走。r的右子树为NULL，因此其高度为0。

所以r有一个高度为1(左)的子树和一个高度为0(右)的子树。我们选择较高的子树的高度并添加1。

return 1 + Math.max(leftHeight, rightHeight);
// pick higher subtree and add 1 to its height
// to include the root node.

因此根在r的树的高度为2。

注意这里没有涉及到循环，只有递归。该问题通过先求解每个(较小的)子树的问题并将结果组合来解决。