BST中的第二个最大值 [英] Second max in BST

问题描述

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

This is an interview question. Find the second max in BST.

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

The max element is the rightmost leaf in the BST. The second max is either its parent or its left child. So the solution is to traverse the BST to find the rightmost leaf and check its parent and left child.

这有意义吗?

推荐答案

回想一下，您可以通过执行修改后的

Recall that you can list the nodes of a BST in reverse order by doing a modified inorder traversal where you explore the right subtree first. This leads to a simple algorithm:

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

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

It would return null if the tree has only one element.

这篇关于BST中的第二个最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！