Node que tiene un número máximo de Nodes menor que su valor en su subárbol

Posted on by Rudeus Greyrat

Dado un árbol binario , la tarea es encontrar el Node del árbol dado que tiene el número máximo de Nodes en su subárbol con valores menores que el valor de ese Node. En el caso de múltiples Nodes posibles con el mismo número de Nodes máximos, devuelva cualquiera de esos Nodes.

Ejemplos:

Aporte:

           4
       / \
     6 10
  / \ / \
2 3 7 14
    /
   5 
  
Salida: 6
Explicación:
El Node con valor 6 tiene el máximo de Nodes que son menores que 6 en el subárbol de 6 como (2, 3, 5), es decir, 3 .

Entrada: 
         10
       /    
    21 
  / \   
2 4 
        \
        11

Salida: 21
Explicación:
El Node con valor 21 tiene el máximo de Nodes que son menores que 21 en el subárbol de 21 como (2, 4, 11), es decir, 3.

Enfoque: La idea es utilizar el recorrido Post Order . A continuación se muestran los pasos:

  1. Realice el Post Order Traversal en el árbol dado.
  2. Compare los Nodes del subárbol izquierdo y el subárbol derecho con su valor raíz y si es menor que el valor de la raíz y almacene los Nodes que son menores que el Node raíz.
  3. Usando el paso anterior en cada Node, encuentre la cantidad de Nodes, luego elija el Node que tenga la cantidad máxima de Nodes cuyas claves sean menores que el Node actual.
  4. Después del recorrido anterior, imprima ese Node que tiene el recuento máximo de valor de Node menor que esos Nodes.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the nodes to be deleted
unordered_map<int, bool> mp;
 
// Structure of a Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// Function to compare the current node
// key with keys received from it left
// & right tree by Post Order traversal
vector<int> findNodes(Node* root, int& max_v,
                      int& rootIndex)
{
    // Base Case
    if (!root) {
        return vector<int>{};
    }
 
    // Find nodes lesser than the current
    // root in the left subtree
    vector<int> left
        = findNodes(root->left, max_v,
                    rootIndex);
 
    // Find nodes lesser than the current
    // root in the right subtree
    vector<int> right
        = findNodes(root->right, max_v,
                    rootIndex);
 
    // Stores all the nodes less than
    // the current node's
    vector<int> combined;
    int count = 0;
 
    // Add the nodes which are less
    // than current node in left[]
    for (int i = 0;
         i < left.size(); i++) {
 
        if (left[i] < root->key) {
            count += 1;
        }
        combined.push_back(left[i]);
    }
 
    // Add the nodes which are less
    // than current node in right[]
    for (int i = 0;
         i < right.size(); i++) {
 
        if (right[i] < root->key) {
            count += 1;
        }
        combined.push_back(right[i]);
    }
 
    // Create a combined vector for
    // pass to it's parent
    combined.push_back(root->key);
 
    // Stores key that has maximum nodes
    if (count > max_v) {
        rootIndex = root->key;
        max_v = count;
    }
 
    // Return the vector of nodes
    return combined;
}
 
// Driver Code
int main()
{
    /*
              3
           /     \
           4        6
         /  \     /   \
       10    2   4     5
    */
 
    // Given Tree
    Node* root = newNode(3);
    root->left = newNode(4);
    root->right = newNode(6);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(10);
    root->left->right = newNode(2);
 
    int max_v = 0;
    int rootIndex = -1;
 
    // Function Call
    findNodes(root, max_v, rootIndex);
 
    // Print the node value
    cout << rootIndex;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Stores the nodes to be deleted
static HashMap<Integer,
               Boolean> mp = new HashMap<Integer,
                                         Boolean>();
static int max_v, rootIndex;
// Structure of a Tree node
static class Node
{
  int key;
  Node left, right;
};
 
// Function to create a new node
static Node newNode(int key)
{
  Node temp = new Node();
  temp.key = key;
  temp.left = temp.right = null;
  return (temp);
}
 
// Function to compare the current node
// key with keys received from it left
// & right tree by Post Order traversal
static Vector<Integer> findNodes(Node root)
{
  // Base Case
  if (root == null)
  {
    return new Vector<Integer>();
  }
 
  // Find nodes lesser than the current
  // root in the left subtree
  Vector<Integer> left = findNodes(root.left);
 
  // Find nodes lesser than the current
  // root in the right subtree
  Vector<Integer> right = findNodes(root.right);
 
  // Stores all the nodes less than
  // the current node's
  Vector<Integer> combined = new Vector<Integer>();
  int count = 0;
 
  // Add the nodes which are less
  // than current node in left[]
  for (int i = 0; i < left.size(); i++)
  {
    if (left.get(i) < root.key)
    {
      count += 1;
    }
    combined.add(left.get(i));
  }
 
  // Add the nodes which are less
  // than current node in right[]
  for (int i = 0; i < right.size(); i++)
  {
    if (right.get(i) < root.key)
    {
      count += 1;
    }
    combined.add(right.get(i));
  }
 
  // Create a combined vector for
  // pass to it's parent
  combined.add(root.key);
 
  // Stores key that has maximum nodes
  if (count > max_v)
  {
    rootIndex = root.key;
    max_v = count;
  }
 
  // Return the vector of nodes
  return combined;
}
 
// Driver Code
public static void main(String[] args)
{
  /*
              3
           /     \
          4       6
         /  \    /  \
       10    2  4    5
    */
 
  // Given Tree
  Node root = newNode(3);
  root.left = newNode(4);
  root.right = newNode(6);
  root.right.left = newNode(4);
  root.right.right = newNode(5);
  root.left.left = newNode(10);
  root.left.right = newNode(2);
 
  max_v = 0;
  rootIndex = -1;
 
  // Function Call
  findNodes(root);
 
  // Print the node value
  System.out.print(rootIndex);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
 
# Stores the nodes to be deleted
max_v = 0
rootIndex  = 0
mp = {}
 
# Structure of a Tree node
class newNode:
     
    def __init__(self, key):
         
        self.key = key
        self.left = None
        self.right = None
 
# Function to compare the current node
# key with keys received from it left
# & right tree by Post Order traversal
def findNodes(root):
     
    global max_v
    global rootIndex
    global mp
     
    # Base Case
    if (root == None):
        return []
 
    # Find nodes lesser than the current
    # root in the left subtree
    left = findNodes(root.left)
 
    # Find nodes lesser than the current
    # root in the right subtree
    right = findNodes(root.right)
 
    # Stores all the nodes less than
    # the current node's
    combined = []
    count = 0
 
    # Add the nodes which are less
    # than current node in left[]
    for i in range(len(left)):
        if (left[i] < root.key):
            count += 1
             
        combined.append(left[i])
 
    # Add the nodes which are less
    # than current node in right[]
    for i in range(len(right)):
        if (right[i] < root.key):
            count += 1
             
        combined.append(right[i])
 
    # Create a combined vector for
    # pass to it's parent
    combined.append(root.key)
 
    # Stores key that has maximum nodes
    if (count > max_v):
        rootIndex = root.key
        max_v = count
 
    # Return the vector of nodes
    return combined
 
# Driver Code
if __name__ == '__main__':
     
    '''
               3
            /     \
           4       6
          / \     / \
        10   2   4   5
    '''
 
    # Given Tree
    root = None
    root = newNode(3)
    root.left = newNode(4)
    root.right = newNode(6)
    root.right.left = newNode(4)
    root.right.right = newNode(5)
    root.left.left = newNode(10)
    root.left.right = newNode(2)
 
    max_v = 0
    rootIndex = -1
 
    # Function Call
    findNodes(root)
 
    # Print the node value
    print(rootIndex)
 
# This code is contributed by ipg2016107

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Stores the nodes to be deleted
static Dictionary<int,
                  Boolean> mp = new Dictionary<int,
                                               Boolean>();
static int max_v, rootIndex;
 
// Structure of a Tree node
class Node
{
    public int key;
    public Node left, right;
};
 
// Function to create a new node
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return (temp);
}
 
// Function to compare the current node
// key with keys received from it left
// & right tree by Post Order traversal
static List<int> findNodes(Node root)
{
     
    // Base Case
    if (root == null)
    {
        return new List<int>();
    }
     
    // Find nodes lesser than the current
    // root in the left subtree
    List<int> left = findNodes(root.left);
     
    // Find nodes lesser than the current
    // root in the right subtree
    List<int> right = findNodes(root.right);
     
    // Stores all the nodes less than
    // the current node's
    List<int> combined = new List<int>();
    int count = 0;
     
    // Add the nodes which are less
    // than current node in []left
    for(int i = 0; i < left.Count; i++)
    {
        if (left[i] < root.key)
        {
            count += 1;
        }
        combined.Add(left[i]);
    }
     
    // Add the nodes which are less
    // than current node in []right
    for(int i = 0; i < right.Count; i++)
    {
        if (right[i] < root.key)
        {
            count += 1;
        }
        combined.Add(right[i]);
    }
     
    // Create a combined vector for
    // pass to it's parent
    combined.Add(root.key);
     
    // Stores key that has maximum nodes
    if (count > max_v)
    {
        rootIndex = root.key;
        max_v = count;
    }
     
    // Return the vector of nodes
    return combined;
}
 
// Driver Code
public static void Main(String[] args)
{
    /*
               3
            /     \
           4      6
          / \    / \
        10   2  4   5
        */
     
    // Given Tree
    Node root = newNode(3);
    root.left = newNode(4);
    root.right = newNode(6);
    root.right.left = newNode(4);
    root.right.right = newNode(5);
    root.left.left = newNode(10);
    root.left.right = newNode(2);
     
    max_v = 0;
    rootIndex = -1;
     
    // Function call
    findNodes(root);
     
    // Print the node value
    Console.Write(rootIndex);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
    // JavaScript program for the above approach
     
    // Stores the nodes to be deleted
    let mp = new Map();
     
    let max_v, rootIndex;
     
    // Structure of a Tree node
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.key = key;
        }
    }
 
    // Function to create a new node
    function newNode(key)
    {
      let temp = new Node(key);
      return (temp);
    }
 
    // Function to compare the current node
    // key with keys received from it left
    // & right tree by Post Order traversal
    function findNodes(root)
    {
      // Base Case
      if (root == null)
      {
        return [];
      }
 
      // Find nodes lesser than the current
      // root in the left subtree
      let left = findNodes(root.left);
 
      // Find nodes lesser than the current
      // root in the right subtree
      let right = findNodes(root.right);
 
      // Stores all the nodes less than
      // the current node's
      let combined = [];
      let count = 0;
 
      // Add the nodes which are less
      // than current node in left[]
      for (let i = 0; i < left.length; i++)
      {
        if (left[i] < root.key)
        {
          count += 1;
        }
        combined.push(left[i]);
      }
 
      // Add the nodes which are less
      // than current node in right[]
      for (let i = 0; i < right.length; i++)
      {
        if (right[i] < root.key)
        {
          count += 1;
        }
        combined.push(right[i]);
      }
 
      // Create a combined vector for
      // pass to it's parent
      combined.push(root.key);
 
      // Stores key that has maximum nodes
      if (count > max_v)
      {
        rootIndex = root.key;
        max_v = count;
      }
 
      // Return the vector of nodes
      return combined;
    }
     
    /*
              3
           /     \
          4       6
         /  \    /  \
       10    2  4    5
    */
  
    // Given Tree
    let root = newNode(3);
    root.left = newNode(4);
    root.right = newNode(6);
    root.right.left = newNode(4);
    root.right.right = newNode(5);
    root.left.left = newNode(10);
    root.left.right = newNode(2);
 
    max_v = 0;
    rootIndex = -1;
 
    // Function Call
    findNodes(root);
 
    // Print the node value
    document.write(rootIndex);
    
</script>
Producción: 

6

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por arpit7714 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 *