Suma de K elementos más grandes en BST usando O(1) Espacio extra

Dado un BST, la tarea es encontrar la suma de todos los elementos mayores o iguales al K-ésimo elemento más grande en el espacio O(1).
Ejemplos: 

Input : K = 3
              8
            /   \
           7     10
         /      /   \
        2      9     13
Output : 32
Explanation: 3rd largest element is 9 so sum of all
             elements greater than or equal to 9 are
             9 + 10 + 13 = 32.

Input : K = 2
           8
         /   \
        5    11
      /  \
     2    7
      \
       3
Output : 19
Explanation: 2nd largest element is 8 so sum of all
             elements greater than or equal to 8 are
             8 + 11 = 19.

Enfoque: el enfoque aquí es hacer un recorrido en orden inverso y, mientras lo hace, simplemente llevar la cuenta del número de Nodes visitados. Hasta que el recuento de Nodes visitados sea inferior a K, continúe agregando los datos del Node actual. Use el hecho de que el recorrido en orden inverso de un BST nos da una lista que se ordena en orden decreciente. Pero el enfoque recursivo o basado en pila/cola para realizar un recorrido inverso en orden porque ambas técnicas consumen O(n) memoria adicional, en su lugar utilizan Reverse Morris Traversal para realizar un recorrido inorder tree, que es un método eficiente en memoria y más rápido para hacer Recorrido de árbol en orden inverso basado en árboles binarios enhebrados.
A continuación se muestra el algoritmo: 

1) Initialize Current as root.
2) Initialize a "count" and "sum" variable to 0.
3) While current is not NULL :
   3.1) If the current has no right child
      a) Increment count and check if count is less than or equal to K.
        1) Simply add the current node's data in "sum" variable.
      b) Otherwise, Move to the left child of current.

   3.2) Else, here we have 2 cases:
      a) Find the inorder successor of current Node. 
         Inorder successor is the left most Node 
         in the right subtree or right child itself.

      b) If the left child of the inorder successor is NULL:
         1) Set current as the left child of its inorder successor.
         2) Move current Node to its right child.

      c) Else, if the threaded link between the current Node 
         and it's inorder successor already exists :
         1) Set left pointer of the inorder successor as NULL.
         2) Increment count and check if the count is less than or equal to K.
            2.a) Simply add the current node's data in "sum" variable.
         3) Otherwise, Move current to it's left child.

4)After the traversal is complete simply return the sum.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find sum of
// K largest elements in BST using
// Reverse Morris Traversal
#include <bits/stdc++.h>
using namespace std;
 
struct node {
    int data;
    struct node *left, *right;
};
 
// Add a new node
node* newNode(int item)
{
    node* temp = new node;
    temp->data = item;
    temp->left = temp->right = NULL;
 
    return temp;
}
 
// Function to find the sum of the K largest elements
// space efficient method used
int SumKLargestUsingReverseMorrisTraversal(node* root, int k)
{
    node* curr = root;
    int sum = 0;
    int count = 0;
 
    // while doing reverse inorder traversal
    // keep track of visited nodes
    while (curr) {
        if (curr->right == NULL) {
 
            // till count is less than k
            if (++count <= k) {
                sum += curr->data;
            }
 
            curr = curr->left;
        }
 
        else {
            // finding the inorder successor node
            // inorder successor is the left most in right subtree
            node* succ = curr->right;
            while (succ->left && succ->left != curr)
                succ = succ->left;
 
            if (succ->left == NULL) {
                succ->left = curr;
 
                curr = curr->right;
            }
 
            // if the threaded link already exists then simply
            // revert back the tree to original form.
            else {
                succ->left = NULL;
 
                if (++count <= k)
                    sum += curr->data;
 
                curr = curr->left;
            }
        }
    }
 
    return sum;
}
 
// Driver Code
int main()
{
    /* Constructed binary tree is
          8
        /   \
       7     10
     /      /  \
    2      9    13
*/
 
    struct node* root = newNode(8);
 
    root->right = newNode(10);
    root->left = newNode(7);
    root->left->left = newNode(2);
 
    root->right->left = newNode(9);
    root->right->right = newNode(13);
 
    cout << SumKLargestUsingReverseMorrisTraversal(root, 3);
 
    return 0;
}

Java

// Java program to find sum of
// K largest elements in BST using
// Reverse Morris Traversal
class GFG
{
static class node
{
    int data;
    node left, right;
};
 
// Add a new node
static node newNode(int item)
{
    node temp = new node();
    temp.data = item;
    temp.left = temp.right = null;
 
    return temp;
}
 
// Function to find the sum of the K largest elements
// space efficient method used
static int SumKLargestUsingReverseMorrisTraversal(node root, int k)
{
    node curr = root;
    int sum = 0;
    int count = 0;
 
    // while doing reverse inorder traversal
    // keep track of visited nodes
    while (curr != null)
    {
        if (curr.right == null)
        {
 
            // till count is less than k
            if (++count <= k)
            {
                sum += curr.data;
            }
 
            curr = curr.left;
        }
 
        else
        {
            // finding the inorder successor node
            // inorder successor is the left most in right subtree
            node succ = curr.right;
            while (succ.left != null && succ.left != curr)
                succ = succ.left;
 
            if (succ.left == null)
            {
                succ.left = curr;
 
                curr = curr.right;
            }
 
            // if the threaded link already exists then simply
            // revert back the tree to original form.
            else
            {
                succ.left = null;
 
                if (++count <= k)
                    sum += curr.data;
 
                curr = curr.left;
            }
        }
    }
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
    /* Constructed binary tree is
       8
      / \
     7     10
    /     / \
    2     9 13 */
    node root = newNode(8);
 
    root.right = newNode(10);
    root.left = newNode(7);
    root.left.left = newNode(2);
 
    root.right.left = newNode(9);
    root.right.right = newNode(13);
 
    System.out.println(SumKLargestUsingReverseMorrisTraversal(root, 3));
    }
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find sum of
# K largest elements in BST using
# Reverse Morris Traversal
class node:
 
    def __init__(self, data):
 
        self.data = data
        self.left = None
        self.right = None
     
# Add a new node
def newNode(item):
 
    temp = node(item)
    return temp
 
# Function to find the sum of
# the K largest elements
# space efficient method used
def SumKLargestUsingReverseMorrisTraversal(root, k):
 
    curr = root
    sum = 0
    count = 0
 
    # while doing reverse inorder traversal
    # keep track of visited nodes
    while (curr):
        if (curr.right == None):
 
            # till count is less than k
            count += 1
            if (count <= k):
                sum += curr.data
 
            curr = curr.left
 
        else:
 
            # finding the inorder successor node
            # inorder successor is the left most
            # in right subtree
            succ = curr.right
            while (succ.left and
                   succ.left != curr):
                succ = succ.left
 
            if (succ.left == None):
                succ.left = curr
                curr = curr.right
         
            # if the threaded link already exists
            # then simply revert back the tree to
            # original form.
            else:
                succ.left = None
                count += 1
                if (count <= k):
                    sum += curr.data
 
                curr = curr.left
    return sum
 
# Driver code
if __name__ == "__main__":
 
    ''' Constructed binary tree is
          8
        /   \
       7     10
     /      /  \
    2      9    13 '''
 
    root = newNode(8)
 
    root.right = newNode(10)
    root.left = newNode(7)
    root.left.left = newNode(2)
 
    root.right.left = newNode(9)
    root.right.right = newNode(13)
 
    print(SumKLargestUsingReverseMorrisTraversal(root, 3))
 
# This code is contributed by Rutvik_56

C#

// C# program to find sum of
// K largest elements in BST using
// Reverse Morris Traversal
using System;
 
class GFG
{
public class node
{
    public int data;
    public node left, right;
};
 
// Add a new node
static node newNode(int item)
{
    node temp = new node();
    temp.data = item;
    temp.left = temp.right = null;
 
    return temp;
}
 
// Function to find the sum of the K largest elements
// space efficient method used
static int SumKLargestUsingReverseMorrisTraversal(node root, int k)
{
    node curr = root;
    int sum = 0;
    int count = 0;
 
    // while doing reverse inorder traversal
    // keep track of visited nodes
    while (curr != null)
    {
        if (curr.right == null)
        {
 
            // till count is less than k
            if (++count <= k)
            {
                sum += curr.data;
            }
 
            curr = curr.left;
        }
 
        else
        {
            // finding the inorder successor node
            // inorder successor is the left most in right subtree
            node succ = curr.right;
            while (succ.left != null && succ.left != curr)
                succ = succ.left;
 
            if (succ.left == null)
            {
                succ.left = curr;
 
                curr = curr.right;
            }
 
            // if the threaded link already exists then simply
            // revert back the tree to original form.
            else
            {
                succ.left = null;
 
                if (++count <= k)
                    sum += curr.data;
 
                curr = curr.left;
            }
        }
    }
    return sum;
}
 
// Driver Code
public static void Main(String[] args)
{
    /* Constructed binary tree is
    8
    / \
    7     10
    /     / \
    2     9 13 */
    node root = newNode(8);
 
    root.right = newNode(10);
    root.left = newNode(7);
    root.left.left = newNode(2);
 
    root.right.left = newNode(9);
    root.right.right = newNode(13);
 
    Console.WriteLine(SumKLargestUsingReverseMorrisTraversal(root, 3));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program to find sum of
// K largest elements in BST using
// Reverse Morris Traversal
 
class node
{
    constructor()
    {
        this.data = 0;
        this.left = this.right = null;
    }
}
 
// Add a new node
function newNode(item)
{
    let temp = new node();
    temp.data = item;
    temp.left = temp.right = null;
  
    return temp;
}
 
// Function to find the sum of the K largest elements
// space efficient method used
function SumKLargestUsingReverseMorrisTraversal(root,k)
{
    let  curr = root;
    let sum = 0;
    let count = 0;
  
    // while doing reverse inorder traversal
    // keep track of visited nodes
    while (curr != null)
    {
        if (curr.right == null)
        {
  
            // till count is less than k
            if (++count <= k)
            {
                sum += curr.data;
            }
  
            curr = curr.left;
        }
  
        else
        {
            // finding the inorder successor node
            // inorder successor is the left most in right subtree
            let succ = curr.right;
            while (succ.left != null && succ.left != curr)
                succ = succ.left;
  
            if (succ.left == null)
            {
                succ.left = curr;
  
                curr = curr.right;
            }
  
            // if the threaded link already exists then simply
            // revert back the tree to original form.
            else
            {
                succ.left = null;
  
                if (++count <= k)
                    sum += curr.data;
  
                curr = curr.left;
            }
        }
    }
    return sum;
}
 
 
// Driver Code
/* Constructed binary tree is
       8
      / \
     7     10
    /     / \
    2     9 13 */
let root = newNode(8);
 
root.right = newNode(10);
root.left = newNode(7);
root.left.left = newNode(2);
 
root.right.left = newNode(9);
root.right.right = newNode(13);
 
document.write(SumKLargestUsingReverseMorrisTraversal(root, 3));
 
 
// This code is contributed by rag2127
</script>
Producción: 

32

 

Complejidad de tiempo: O(N) 
Complejidad de espacio: O(1) 
 

Publicación traducida automáticamente

Artículo escrito por AnishSinghWalia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *