Encuentre el máximo entre todos los Nodes correctos en Binary Tree

Dado un árbol binario. La tarea es encontrar el valor máximo entre todos los Nodes secundarios correctos del árbol binario.
Nota : si el árbol no contiene ningún Node secundario derecho o está vacío, imprima -1.
Ejemplos
 

Input : 
           7
         /    \
        6       5
       / \     / \
      4  3     2  1 
Output : 5
All possible right child nodes are: {3, 5, 1}
out of which 5 is of the maximum value.

Input :
            1
         /    \
        2       3
       /       / \
      4       5   6
        \    /  \ 
         7  8    9 
Output : 9

La idea es recorrer recursivamente el árbol con un recorrido en orden y para cada Node: 
 

  • Compruebe si existe el Node secundario correcto.
  • En caso afirmativo, almacene su valor en una variable temporal.
  • Devuelve el máximo entre (valor del Node secundario derecho del Node actual, llamada recursiva para el subárbol izquierdo, llamada recursiva para el subárbol derecho).

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

C++

// CPP program to print maximum element
// among all right child nodes
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
};
 
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Function to find maximum element
// among all right child nodes using
// Inorder Traversal
int maxOfRightElement(Node* root)
{
    // Temp variable
    int res = INT_MIN;
 
    // If tree is empty
    if (root == NULL)
        return -1;
 
    // If right child exists
    if (root->right != NULL)
        res = root->right->data;
 
    // Return maximum of three values
    // 1) Recursive max in right subtree
    // 2) Value in right child node
    // 3) Recursive max in left subtree
    return max({ maxOfRightElement(root->right),
                 res,
                 maxOfRightElement(root->left) });
}
 
// Driver Code
int main()
{
    // Create binary tree
    // as shown below
 
    /*   7
        / \
       6   5
      / \ / \
      4 3 2 1  */
    Node* root = newNode(7);
    root->left = newNode(6);
    root->right = newNode(5);
    root->left->left = newNode(4);
    root->left->right = newNode(3);
    root->right->left = newNode(2);
    root->right->right = newNode(1);
 
    cout << maxOfRightElement(root);
 
    return 0;
}

Java

// Java implementation to print maximum element
// among all right child nodes
import java.io.*;
import java.util.*;
 
// User defined node class
class Node {
      int data;
      Node left, right;
      // Constructor to create a new tree node
      Node(int key)
      {
           data = key;
           left = right = null;
      }
}
class GFG {
      static int maxOfRightElement(Node root)
      {
             // Temp variable
             int res = Integer.MIN_VALUE;
 
             // If tree is empty
             if (root == null)
                 return -1;
              
              // If right child exists
              if (root.right != null)
                  res = root.right.data;
 
              // Return maximum of three values
              // 1) Recursive max in right subtree
              // 2) Value in right child node
              // 3) Recursive max in left subtree
              return Math.max(maxOfRightElement(root.right),
                     Math.max(res,maxOfRightElement(root.left)));
      }
      // Driver code
      public static void main(String args[])
      {
           // Create binary tree
          // as shown below
 
          /*   7
              / \
             6   5
            / \ / \
            4 3 2  1  */
      
          Node root = new Node(7);
          root.left = new Node(6);
          root.right = new Node(5);
          root.left.left = new Node(4);
          root.left.right = new Node(3);
          root.right.left = new Node(2);
          root.right.right = new Node(1);
  
          System.out.println(maxOfRightElement(root));
       }
}
// This code is contributed by rachana soma

Python3

# Python3 program to print maximum element
# among all right child nodes
 
# Tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Utility function to create a new tree node
def newNode(data):
 
    temp = Node(0)
    temp.data = data
    temp.left = temp.right = None
    return temp
 
# Function to find maximum element
# among all right child nodes using
# Inorder Traversal
def maxOfRightElement(root):
 
    # Temp variable
    res = -999999
 
    # If tree is empty
    if (root == None):
        return -1
 
    # If right child exists
    if (root.right != None):
        res = root.right.data
 
    # Return maximum of three values
    # 1) Recursive max in right subtree
    # 2) Value in right child node
    # 3) Recursive max in left subtree
    return max( maxOfRightElement(root.right),
                res,
                maxOfRightElement(root.left) )
 
# Driver Code
 
# Create binary tree
# as shown below
#     7
# / \
# 6 5
# / \ / \
# 4 3 2 1
root = newNode(7)
root.left = newNode(6)
root.right = newNode(5)
root.left.left = newNode(4)
root.left.right = newNode(3)
root.right.left = newNode(2)
root.right.right = newNode(1)
 
print (maxOfRightElement(root))
 
# This code is contributed by Arnab Kundu

C#

// C# implementation to print maximum element
// among all right child nodes
using System;
 
// User defined node class
public class Node
{
    public int data;
    public Node left, right;
     
    // Constructor to create a new tree node
    public Node(int key)
    {
        data = key;
        left = right = null;
    }
}
 
public class GFG
{
    static int maxOfRightElement(Node root)
    {
            // Temp variable
            int res = int.MinValue;
 
            // If tree is empty
            if (root == null)
                return -1;
             
            // If right child exists
            if (root.right != null)
                res = root.right.data;
 
            // Return maximum of three values
            // 1) Recursive max in right subtree
            // 2) Value in right child node
            // 3) Recursive max in left subtree
            return Math.Max(maxOfRightElement(root.right),
                    Math.Max(res,maxOfRightElement(root.left)));
    }
     
    // Driver code
    public static void Main(String []args)
    {
        // Create binary tree
        // as shown below
 
        /* 7
            / \
            6 5
            / \ / \
            4 3 2 1 */
     
        Node root = new Node(7);
        root.left = new Node(6);
        root.right = new Node(5);
        root.left.left = new Node(4);
        root.left.right = new Node(3);
        root.right.left = new Node(2);
        root.right.right = new Node(1);
 
        Console.WriteLine(maxOfRightElement(root));
    }
}
 
// This code is contributed 29AjayKumar

Javascript

<script>
 
    // JavaScript implementation to print maximum element
    // among all right child nodes
     
    // User defined node class
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.data = key;
        }
    }
     
    function maxOfRightElement(root)
    {
      // Temp variable
      let res = Number.MIN_VALUE;
 
      // If tree is empty
      if (root == null)
        return -1;
 
      // If right child exists
      if (root.right != null)
        res = root.right.data;
 
      // Return maximum of three values
      // 1) Recursive max in right subtree
      // 2) Value in right child node
      // 3) Recursive max in left subtree
      return Math.max(maxOfRightElement(root.right),
                      Math.max(res,maxOfRightElement(root.left)));
    }
     
    // Create binary tree
    // as shown below
 
    /*   7
                / \
               6   5
              / \ / \
              4 3 2  1  */
 
    let root = new Node(7);
    root.left = new Node(6);
    root.right = new Node(5);
    root.left.left = new Node(4);
    root.left.right = new Node(3);
    root.right.left = new Node(2);
    root.right.right = new Node(1);
 
    document.write(maxOfRightElement(root));
 
</script>
Producción: 

5

 

Tiempo Complejidad : O(n) Espacio Auxiliar : O(n)  

Publicación traducida automáticamente

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