递归过程如何计算 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);

}

如果根的左child或右child不为空，则再次调用相同的高度方法，递归进行。否则，它 returns 为零。我很难理解如何计算增加（比如，像 c +=1 你看到它为每个循环增加 1）。

谁能详细给我解释一下？

Answer 1

此处计数增加：

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

因为每次递归调用 returns 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，这也是我们return备份到r的高度：[=的高度14=]的左子树是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。

请注意，不涉及循环，仅涉及递归。通过首先解决每个（较小的）子树的问题并合并结果来解决问题。

递归过程如何计算 BST 的高度？

How the recursive procedure works for computing height of the BST?

java

recursion

binary-search-tree

data-structures