algorithm - BST中的第二个最大值

这是一个面试问题。在BST中找到第二个最大值。

max元素是BST中最右边的叶子。第二个最大值是其父级或左子级。因此，解决方案是遍历BST以找到最右边的叶子并检查其父对象和左 child 。

是否有意义？

最佳答案

回想一下，您可以通过执行修改后的inorder traversal以相反的顺序列出BST的节点，您首先在其中探索正确的子树。这导致了一个简单的算法:

Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
    return findRightmostNode(rightmost.left)
else{
    return rightmost.parent
}

如果树只有一个元素，它将返回null。