Seconde max dans BST

Rappelez-vous que vous pouvez lister les nœuds d'un BST dans l'ordre inverse en faisant une modification de afinde traversée qui vous propose d'explorer le sous-arbre droit en premier. Cela conduit à un algorithme simple:

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

Il serait de retour la valeur null si l'arbre a un seul élément.

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;
    }

Beaucoup plus facile d'approche itérative, avec le Temps, la complexité O(logN) et de l'Espace de la complexité 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;

        }

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);
}

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;
}

Javascript Simple de mise en œuvre.

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);

Cet algorithme fait un run sur l'arbre et retourne le plus grand élément à Item1 et le deuxième plus grand au Item2.
Le tri des appels sont O(1) parce qu'ils sont indépendants de la taille de l'arbre.
De sorte que le total temps de la complexité est O(N) et espace complexité est O(log(N)) lorsque l'arbre est équilibré.

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]);
    }
}