这是一道面试题。在 BST 中找到第二个最大值。
最大元素是 BST 中最右边的叶子。第二个最大值是它的父节点或左子节点。所以解决的办法是遍历BST找到最右边的叶子，检查它的父节点和左子节点。
是否有意义？
问问题
21720 次
15 回答
31
不，那是错误的。考虑这个 BST：
137
/
42
\
99
这里，第二个到最大值是最大值的左孩子的最右边的孩子。您的算法将需要更新，以便您检查最大值的父项，或最大值左子项的最右边子项。
另外，请注意，最大值不一定是最右边的叶节点，它是树右脊底部的节点。上面，137 不是一片叶子。
希望这可以帮助！
于 2012-07-11T04:16:18.050 回答
15
回想一下，您可以通过在首先探索右子树的地方进行修改后的中序遍历来以相反的顺序列出 BST 的节点。这导致了一个简单的算法：
Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
return findRightmostNode(rightmost.left)
else{
return rightmost.parent
}
如果树只有一个元素，它将返回 null。
于 2012-07-11T04:24:48.140 回答
10
public static int findSecondLargestValueInBST(Node root)
{
int secondMax;
Node pre = root;
Node cur = root;
while (cur.Right != null)
{
pre = cur;
cur = cur.Right;
}
if (cur.Left != null)
{
cur = cur.Left;
while (cur.Right != null)
cur = cur.Right;
secondMax = cur.Value;
}
else
{
if (cur == root && pre == root)
//Only one node in BST
secondMax = int.MinValue;
else
secondMax = pre.Value;
}
return secondMax;
}
于 2013-04-10T21:43:38.637 回答
7
时间复杂度O(logN)和空间复杂度O(1)的更简单的迭代方法
public static void main(String[] args) {
BinaryTreeNode result=isBinarySearchTree.secondLargest(rootNode);
System.out.println(result.data);
}
private BinaryTreeNode secondLargest(BinaryTreeNode node) {
BinaryTreeNode prevNode=null; //2nd largest Element
BinaryTreeNode currNode=node;
if(null == currNode)
return prevNode;
while(currNode.right != null){
prevNode=currNode;
currNode=currNode.right;
}
if(currNode.left != null){
currNode=currNode.left;
while(currNode.right != null){
currNode=currNode.right;
}
prevNode=currNode;
}
return prevNode;
}
于 2017-07-19T05:56:33.647 回答
5
算法可以如下
1. find the largest number in the tree.
private static int findLargestValueInTree(Node root) {
while (root.right != null) {
root = root.right;
}
return root.data;
}
2. Find the largest number in the tree that is smaller than the number we found in step 1
public static int findSecondLargest(Node root, int largest, int current) {
while (root != null) {
if (root.data < largest) {
current = root.data;
root = root.right;
} else {
root = root.left;
}
}
return current;
}
'current' 跟踪当前最大的数字，该数字小于在 step1 中找到的数字
于 2012-08-31T23:55:47.853 回答
2
简单的javascript实现。
function Node (value, left, right) {
this.value = value;
this.left = left;
this.right = right;
}
function second (node, prev, wentLeft) {
if (node.right) {
return second(node.right, node, wentLeft);
} else if (node.left) {
return second(node.left, node, true);
} else {
if (wentLeft) return node.value;
return prev.value;
}
}
second(root);
于 2017-01-02T03:16:26.670 回答
1
一种遍历变体：
public Tree GetSecondMax(Tree root)
{
Tree parentOfMax = null;
var maxNode = GetMaxNode(root, ref parentOfMax);
if (maxNode == root || maxnode.left != null)
{
// if maximum node is root or have left subtree, then return maximum from left subtree
return GetMaxNode(maxnode.left, ref parentOfMax);
}
// if maximum node is not root, then return parent of maximum node
return parentOfMax;
}
private Tree GetMaxNode(Tree root, ref Tree previousNode)
{
if (root == null || root.right == null)
{
// The most right element have reached
return root;
}
// we was there
previousNode = root;
return GetMaxNode(root.right, ref previousNode);
}
于 2013-02-09T13:00:45.713 回答
1
int getmax(node *root)
{
if(root->right == NULL)
{
return root->d;
}
return getmax(root->right);
}
int secondmax(node *root)
{
if(root == NULL)
{
return -1;
}
if(root->right == NULL && root->left != NULL)
{
return getmax(root->left);
}
if(root->right != NULL)
{
if(root->right->right == NULL && root->right->left == NULL)
{
return root->d;
}
}
return secondmax(root->right);
}
于 2013-10-11T21:32:24.043 回答
1
考虑这一点的一种非常直观的方法是考虑以下两种情况。设第二大节点为 S，最大节点为 L。
i) S 比 L“更早”插入到 BST。 ii) S 比 L“晚”插入到 BST。
对于第一种情况，很明显 L 是 S 的右孩子。这是因为除了 L 之外的任何节点都小于 S，因此不会放在 S 的右侧。因此，当放 L 时，它将是 S 的右孩子。
对于第二种情况，当 S 被插入时，L 将是 BST 中最右边的节点。显然，L 不会有正确的孩子，因为它是最大的。但是，L 可以有自己的左子树。当S被插入时，S会沿着“右路”直到遇到L，然后左转去L的左子树。这里，我们知道L的左子树中的所有节点都小于S，所以S将是子树中最右边的节点。
于 2014-09-21T05:09:17.247 回答
1
int getSecondLargest(Node root){
if(root==null)
return 0;
Node curr=root;
Node prev=root;
//Go to the largest node
while(curr.right != null){
prev = curr;
curr= curr.right;
}
//If largest Node has left child, Then largest element of tree with its root as largest.left will be the second largest number.
if(curr.left == null)
return prev.data;
else
return findLargest(curr.left);
}
int findLargest(Node root){
// No need toi check for null condition as in getSecondLargest method, its already done.
Node curr=root;
//To find largest just keep on going to right child till leaf is encountered.
while(curr.right != null){
curr = curr.right;
}
return curr.data;
}
于 2016-06-03T09:02:29.863 回答
1
我会通过从最大到最小元素遍历树并在达到询问位置时返回值来做到这一点。我为第二大价值实施了类似的任务。
void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
if(r->right) {
this->findSecondLargestValueUtil(r->right, c, v);
}
c++;
if(c==2) {
v = r->value;
return;
}
if(r->left) {
this->findSecondLargestValueUtil(r->left, c, v);
}
}
int BTree::findSecondLargestValue()
{
int c = 0;
int v = -1;
this->findSecondLargestValueUtil(this->root, c, v);
return v;
}
于 2016-10-17T22:53:44.293 回答
1
您已接近正确答案。
这是我对直观答案的尝试。
最大节点是最右边的节点。
最右边节点的左子树下的任何内容都大于除最右边节点之外的所有元素。因此，这个子树中的最大节点就是答案。
如果没有左子树，则最右节点的父节点是大于除最右节点之外的所有其他节点的父节点。
于 2017-07-19T06:06:23.363 回答
1
这个想法是一直向右走，直到右边没有任何东西。如果有左边，就走，然后一直向右走。如果您向左走，答案是遇到的最后一个节点。否则，答案是您遇到的倒数第二个节点。
这是Java中的递归解决方案：
public TreeNode getSecondLargest(TreeNode root) {
if(root == null || (root.left == null && root.right == null))
throw new IllegalArgumentException("The tree must have at least two nodes");
return helper(root, null, false);
}
private TreeNode helper(TreeNode root, TreeNode parent, boolean wentLeft) {
if(root.right != null) return helper(root.right, root, wentLeft);
if(root.left != null && !wentLeft) return helper(root.left, root, true);
if(wentLeft) return root;
else return parent;
}
时间复杂度为 O(lg n)。
于 2018-08-12T21:08:21.217 回答
1
这种在 BST 中找到第二个最大元素的算法将花费时间复杂度：O(n) --> 在最坏的情况下，树是右斜树。如果树是平衡树，那么时间复杂度是 O(height) 即 O(log n) 并且空间复杂度也一样：O(n) --> 在最坏的情况下 O(log n) --> 当树是平衡的。
public TreeNode secondMax(TreeNode root){
return helper(root,null);
}
private TreeNode helper(TreeNode root,TreeNode prev){
if(root==null)
return root;
if(root.right==null && root.left!=null)
return root.left;
else if(root.right==null && root.left==null)
return prev;
return helper(root.right,root);
}
于 2020-10-19T09:58:21.247 回答
0
该算法在树上运行一次，并返回在 处的最大项目和在 处的Item1第二大项目Item2。排序调用是O(1)，因为它们与树的大小无关。因此，当树平衡时，总时间复杂度为O(N)，空间复杂度为O(log(N)) 。
public static Tuple<int, int> SecondLargest(TreeNode<int> node)
{
int thisValue = node.Value;
if ((node.Left == null || node.Left.Right == null) && node.Right == null)
{
return new Tuple<int, int>(thisValue, -int.MaxValue);
}
else if (node.Left == null || node.Left.Right == null)
{
Tuple<int, int> right = SecondLargest(node.Right);
List<int> sortLargest = new List<int>(new int[] { right.Item1, right.Item2, thisValue });
sortLargest.Sort();
return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
}
else if (node.Right == null)
{
Tuple<int, int> left = SecondLargest(node.Left.Right);
List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, thisValue });
sortLargest.Sort();
return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
}
else
{
Tuple<int, int> left = SecondLargest(node.Left.Right);
Tuple<int, int> right = SecondLargest(node.Right);
List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, right.Item1, right.Item2, thisValue });
sortLargest.Sort();
return new Tuple<int, int>(sortLargest[4], sortLargest[3]);
}
}
于 2017-02-10T20:03:27.140 回答