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