Dado un árbol binario y dos Nodes a y b , la tarea es imprimir el valor de Node mínimo y máximo que se encuentra en la ruta que conecta los Nodes dados a y b . Si alguno de los dos Nodes no está presente en el árbol, imprima -1 para el valor mínimo y máximo.
Ejemplos:
Input:
1
/ \
2 3
/ \ \
4 5 6
/ / \
7 8 9
a = 5, b = 6
Output:
Min = 1
Max = 6
Input:
20
/ \
8 22
/ \ / \
5 3 4 25
/ \
10 14
a = 5, b = 14
Output:
Min = 3
Max = 14
Enfoque: La idea es encontrar el LCA de ambos Nodes. Luego comience a buscar el Node mínimo y máximo en la ruta desde LCA al primer Node y luego desde LCA al segundo Node e imprima el mínimo y el máximo de estos valores. En caso de que alguno de los Nodes no esté presente en el árbol, imprima -1 para el valor mínimo y máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Structure of binary tree
struct Node {
Node* left;
Node* right;
int data;
};
// Function to create a new node
Node* newNode(int key)
{
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
// Function to store the path from root node
// to given node of the tree in path vector and
// then returns true if the path exists
// otherwise false
bool FindPath(Node* root, vector<int>& path, int key)
{
if (root == NULL)
return false;
path.push_back(root->data);
if (root->data == key)
return true;
if (FindPath(root->left, path, key)
|| FindPath(root->right, path, key))
return true;
path.pop_back();
return false;
}
// Function to print the minimum and the maximum
// value present in the path connecting the
// given two nodes of the given binary tree
int minMaxNodeInPath(Node* root, int a, int b)
{
// To store the path from the root node to a
vector<int> Path1;
// To store the path from the root node to b
vector<int> Path2;
// To store the minimum and the maximum value
// in the path from LCA to a
int min1 = INT_MAX;
int max1 = INT_MIN;
// To store the minimum and the maximum value
// in the path from LCA to b
int min2 = INT_MAX;
int max2 = INT_MIN;
int i = 0;
int j = 0;
// If both a and b are present in the tree
if (FindPath(root, Path1, a) && FindPath(root, Path2, b)) {
// Compare the paths to get the first different value
for (i = 0; i < Path1.size() && Path2.size(); i++)
if (Path1[i] != Path2[i])
break;
i--;
j = i;
// Find minimum and maximum value
// in the path from LCA to a
for (; i < Path1.size(); i++) {
if (min1 > Path1[i])
min1 = Path1[i];
if (max1 < Path1[i])
max1 = Path1[i];
}
// Find minimum and maximum value
// in the path from LCA to b
for (; j < Path2.size(); j++) {
if (min2 > Path2[j])
min2 = Path2[j];
if (max2 < Path2[j])
max2 = Path2[j];
}
// Minimum of min values in first
// path and second path
cout << "Min = " << min(min1, min2) << endl;
// Maximum of max values in first
// path and second path
cout << "Max = " << max(max1, max2);
}
// If no path exists
else
cout << "Min = -1\nMax = -1";
}
// Driver Code
int main()
{
Node* root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(5);
root->left->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(25);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int a = 5;
int b = 1454;
minMaxNodeInPath(root, a, b);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Structure of binary tree
static class Node
{
Node left;
Node right;
int data;
};
// Function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
static Vector<Integer> path;
// Function to store the path from root node
// to given node of the tree in path vector and
// then returns true if the path exists
// otherwise false
static boolean FindPath(Node root, int key)
{
if (root == null)
return false;
path.add(root.data);
if (root.data == key)
return true;
if (FindPath(root.left, key)
|| FindPath(root.right, key))
return true;
path.remove(path.size()-1);
return false;
}
// Function to print the minimum and the maximum
// value present in the path connecting the
// given two nodes of the given binary tree
static int minMaxNodeInPath(Node root, int a, int b)
{
// To store the path from the root node to a
path = new Vector<Integer> ();
boolean flag = true;
// To store the path from the root node to b
Vector<Integer> Path2 = new Vector<Integer>(),
Path1 = new Vector<Integer>();
// To store the minimum and the maximum value
// in the path from LCA to a
int min1 = Integer.MAX_VALUE;
int max1 = Integer.MIN_VALUE;
// To store the minimum and the maximum value
// in the path from LCA to b
int min2 = Integer.MAX_VALUE;
int max2 = Integer.MIN_VALUE;
int i = 0;
int j = 0;
flag = FindPath(root, a);
Path1 = path;
path = new Vector<Integer>();
flag&= FindPath(root, b);
Path2 = path;
// If both a and b are present in the tree
if ( flag)
{
// Compare the paths to get the first different value
for (i = 0; i < Path1.size() && i < Path2.size(); i++)
if (Path1.get(i) != Path2.get(i))
break;
i--;
j = i;
// Find minimum and maximum value
// in the path from LCA to a
for (; i < Path1.size(); i++)
{
if (min1 > Path1.get(i))
min1 = Path1.get(i);
if (max1 < Path1.get(i))
max1 = Path1.get(i);
}
// Find minimum and maximum value
// in the path from LCA to b
for (; j < Path2.size(); j++)
{
if (min2 > Path2.get(j))
min2 = Path2.get(j);
if (max2 < Path2.get(j))
max2 = Path2.get(j);
}
// Minimum of min values in first
// path and second path
System.out.println( "Min = " + Math.min(min1, min2) );
// Maximum of max values in first
// path and second path
System.out.println( "Max = " + Math.max(max1, max2));
}
// If no path exists
else
System.out.println("Min = -1\nMax = -1");
return 0;
}
// Driver Code
public static void main(String args[])
{
Node root = newNode(20);
root.left = newNode(8);
root.right = newNode(22);
root.left.left = newNode(5);
root.left.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(25);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
int a = 5;
int b = 14;
minMaxNodeInPath(root, a, b);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Function to store the path from root
# node to given node of the tree in
# path vector and then returns true if
# the path exists otherwise false
def FindPath(root, path, key):
if root == None:
return False
path.append(root.data)
if root.data == key:
return True
if (FindPath(root.left, path, key) or
FindPath(root.right, path, key)):
return True
path.pop()
return False
# Function to print the minimum and the
# maximum value present in the path
# connecting the given two nodes of the
# given binary tree
def minMaxNodeInPath(root, a, b):
# To store the path from the
# root node to a
Path1 = []
# To store the path from the
# root node to b
Path2 = []
# To store the minimum and the maximum
# value in the path from LCA to a
min1, max1 = float('inf'), float('-inf')
# To store the minimum and the maximum
# value in the path from LCA to b
min2, max2 = float('inf'), float('-inf')
i, j = 0, 0
# If both a and b are present in the tree
if (FindPath(root, Path1, a) and
FindPath(root, Path2, b)):
# Compare the paths to get the
# first different value
while i < len(Path1) and i < len(Path2):
if Path1[i] != Path2[i]:
break
i += 1
i -= 1
j = i
# Find minimum and maximum value
# in the path from LCA to a
while i < len(Path1):
if min1 > Path1[i]:
min1 = Path1[i]
if max1 < Path1[i]:
max1 = Path1[i]
i += 1
# Find minimum and maximum value
# in the path from LCA to b
while j < len(Path2):
if min2 > Path2[j]:
min2 = Path2[j]
if max2 < Path2[j]:
max2 = Path2[j]
j += 1
# Minimum of min values in first
# path and second path
print("Min =", min(min1, min2))
# Maximum of max values in first
# path and second path
print("Max =", max(max1, max2))
# If no path exists
else:
print("Min = -1\nMax = -1")
# Driver Code
if __name__ == "__main__":
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(25)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
a, b = 5, 14
minMaxNodeInPath(root, a, b)
# This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections;
class GFG{
// Structure of binary tree
class Node
{
public Node left;
public Node right;
public int data;
};
// Function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
static ArrayList path;
// Function to store the path from root
// node to given node of the tree in path
// vector and then returns true if the
// path exists otherwise false
static bool FindPath(Node root, int key)
{
if (root == null)
return false;
path.Add(root.data);
if (root.data == key)
return true;
if (FindPath(root.left, key) ||
FindPath(root.right, key))
return true;
path.Remove((int)path[path.Count - 1]);
return false;
}
// Function to print the minimum and the maximum
// value present in the path connecting the
// given two nodes of the given binary tree
static int minMaxNodeInPath(Node root, int a,
int b)
{
// To store the path from the root node to a
path = new ArrayList();
bool flag = true;
// To store the path from the root node to b
ArrayList Path2 = new ArrayList();
ArrayList Path1 = new ArrayList();
// To store the minimum and the maximum value
// in the path from LCA to a
int min1 = Int32.MaxValue;
int max1 = Int32.MinValue;
// To store the minimum and the maximum value
// in the path from LCA to b
int min2 = Int32.MaxValue;
int max2 = Int32.MinValue;
int i = 0;
int j = 0;
flag = FindPath(root, a);
Path1 = path;
path = new ArrayList();
flag &= FindPath(root, b);
Path2 = path;
// If both a and b are present in the tree
if (flag)
{
// Compare the paths to get the
// first different value
for(i = 0; i < Path1.Count &&
i < Path2.Count; i++)
if ((int)Path1[i] != (int)Path2[i])
break;
i--;
j = i;
// Find minimum and maximum value
// in the path from LCA to a
for(; i < Path1.Count; i++)
{
if (min1 > (int)Path1[i])
min1 = (int)Path1[i];
if (max1 < (int)Path1[i])
max1 = (int)Path1[i];
}
// Find minimum and maximum value
// in the path from LCA to b
for(; j < Path2.Count; j++)
{
if (min2 > (int)Path2[j])
min2 = (int)Path2[j];
if (max2 < (int)Path2[j])
max2 = (int)Path2[j];
}
// Minimum of min values in first
// path and second path
Console.Write("Min = " +
Math.Min(min1, min2) + "\n" );
// Maximum of max values in first
// path and second path
Console.Write("Max = " +
Math.Max(max1, max2) + "\n");
}
// If no path exists
else
Console.Write("Min = -1\nMax = -1");
return 0;
}
// Driver Code
public static void Main(string []arg)
{
Node root = newNode(20);
root.left = newNode(8);
root.right = newNode(22);
root.left.left = newNode(5);
root.left.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(25);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
int a = 5;
int b = 14;
minMaxNodeInPath(root, a, b);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript implementation of the approach
// Structure of binary tree
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.data = key;
}
}
// Function to create a new node
function newNode(key)
{
let node = new Node(key);
return node;
}
let path = [];
// Function to store the path from root node
// to given node of the tree in path vector and
// then returns true if the path exists
// otherwise false
function FindPath(root, key)
{
if (root == null)
return false;
path.push(root.data);
if (root.data == key)
return true;
if (FindPath(root.left, key)
|| FindPath(root.right, key))
return true;
path.pop();
return false;
}
// Function to print the minimum and the maximum
// value present in the path connecting the
// given two nodes of the given binary tree
function minMaxNodeInPath(root, a, b)
{
// To store the path from the root node to a
path = [];
let flag = true;
// To store the path from the root node to b
let Path2 = [], Path1 = [];
// To store the minimum and the maximum value
// in the path from LCA to a
let min1 = Number.MAX_VALUE;
let max1 = Number.MIN_VALUE;
// To store the minimum and the maximum value
// in the path from LCA to b
let min2 = Number.MAX_VALUE;
let max2 = Number.MIN_VALUE;
let i = 0;
let j = 0;
flag = FindPath(root, a);
Path1 = path;
path = [];
flag&= FindPath(root, b);
Path2 = path;
// If both a and b are present in the tree
if ( flag)
{
// Compare the paths to get the first different value
for (i = 0; i < Path1.length && i < Path2.length; i++)
if (Path1[i] != Path2[i])
break;
i--;
j = i;
// Find minimum and maximum value
// in the path from LCA to a
for (; i < Path1.length; i++)
{
if (min1 > Path1[i])
min1 = Path1[i];
if (max1 < Path1[i])
max1 = Path1[i];
}
// Find minimum and maximum value
// in the path from LCA to b
for (; j < Path2.length; j++)
{
if (min2 > Path2[j])
min2 = Path2[j];
if (max2 < Path2[j])
max2 = Path2[j];
}
// Minimum of min values in first
// path and second path
document.write( "Min = " + Math.min(min1, min2) +
"</br>");
// Maximum of max values in first
// path and second path
document.write( "Max = " + Math.max(max1, max2) +
"</br>");
}
// If no path exists
else
document.write("Min = -1\nMax = -1" + "</br>");
return 0;
}
let root = newNode(20);
root.left = newNode(8);
root.right = newNode(22);
root.left.left = newNode(5);
root.left.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(25);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
let a = 5;
let b = 14;
minMaxNodeInPath(root, a, b);
</script>
Producción:
Min = 3 Max = 14
Complejidad temporal : O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA