1

我已经看到查找二叉搜索树高度问题的常见解决方案如下所示：

private int getHeight(Node<T> ptr, String typeOfCall)
{
    if (ptr == null)
        return -1;

    int leftHeight = -1;
    int rightHeight = -1;

    System.out.println(input);
    System.out.println("Node value: " + ptr.el);

    if (ptr != null)
        leftHeight = getHeight(ptr.left, "leftHeight Call");
    if (ptr != null)
        rightHeight = getHeight(ptr.right, "rightHeight Call");

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

}

如您所见，我添加了一些额外的代码行以尝试了解此方法的工作原理...

以下面的 BST 为例：

                             99
                            /  \
                          50    100
                         /  \
                       49    55
                      /        \
                     48         60
                    /             \
                   47              70
                                     \ 
                                      80

我添加的代码得到的输出是：

first
Node value: 99
leftHeight Call
Node value: 50
leftHeight Call
Node value: 49
leftHeight Call
Node value: 48
leftHeight Call
Node value: 47
rightHeight Call
Node value: 55
rightHeight Call  
Node value: 60
rightHeight Call
Node value: 70
rightHeight Call
Node value: 80
rightHeight Call
Node value: 100
height: 5

我现在的问题是：函数如何知道它必须从值为 47 的叶节点到值为 55 的节点，然后从那里尽可能地下降？即当ptr 当前指向值为47 的叶节点时，ptr.right.element = 55 如何？我认为 ptr.right 现在将等于 null，因为它位于叶节点上？此外，一旦遇到值为 80 的叶节点 - 该函数将转到右子树。它怎么知道这样做？

任何解释将不胜感激！我觉得这里涉及的递归可能是我困惑的原因。这个功能如何工作？谢谢！

编辑Oli 提出建议后，我在递归函数调用下方添加了一些打印语句。

            private int getHeight(Node<T> ptr, String typeOfCall)
    if (ptr == null)
        return -1;

    int leftHeight = -1;
    int rightHeight = -1;

    System.out.println("Before: " + input);
    System.out.println("Before: " + ptr.el);

    if (ptr != null)
        leftHeight = getHeight(ptr.left, "leftHeight Call");
    if (ptr != null)
        rightHeight = getHeight(ptr.right, "rightHeight Call");

    System.out.println("After Recursive: " + input);
    System.out.println("After Recursive: " + ptr.el);

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

输出：

Before: first
Before: 99
Before: leftHeight Call
Before: 50
Before: leftHeight Call
Before: 49
Before: leftHeight Call
Before: 48
Before: leftHeight Call
Before: 47
After Recursive: leftHeight Call
After Recursive: 47
After Recursive: leftHeight Call
After Recursive: 48
After Recursive: leftHeight Call
After Recursive: 49
Before: rightHeight Call
Before: 55
Before: rightHeight Call
Before: 60
Before: rightHeight Call
Before: 70
Before: rightHeight Call
Before: 80  
After Recursive: rightHeight Call
After Recursive: 80
After Recursive: rightHeight Call
After Recursive: 70
After Recursive: rightHeight Call
After Recursive: 60
After Recursive: rightHeight Call
After Recursive: 55
After Recursive: leftHeight Call 
After Recursive: 50
Before: rightHeight Call
Before: 100
After Recursive: rightHeight Call
Below Recursive: 100
Below Recursive: first
Below Recursive: 99

这真的有助于理解这里使用的递归的展开以及这个函数作为一个整体是如何工作的。

4

0 回答 0