Dado un árbol binario , la tarea es encontrar la longitud del camino más largo que forma una progresión aritmética . La ruta puede comenzar y terminar en cualquier Node del árbol.
Ejemplos:
Aporte:
Salida: 5
Explicación: El camino más largo que forma un AP es: 3->6->9->12->15Aporte:
Salida: 6
Explicación: El camino más largo que forma un AP es: 2->4->6->8->10->12
Enfoque: el problema aquí es que un Node de árbol solo puede admitir dos AP, uno con el hijo izquierdo y el otro con el hijo derecho. Ahora, para resolver este problema, siga los siguientes pasos:
- Cree una variable ans para almacenar la longitud de la ruta más larga.
- Inicie una búsqueda en profundidad desde el Node raíz y, para cada Node, busque la ruta de longitud máxima de los puntos de acceso hasta el hijo izquierdo y el hijo derecho.
- Ahora encuentre la diferencia entre el Node actual y su hijo izquierdo, digamos leftDiff y la diferencia entre el Node actual y su hijo derecho, digamos rightDiff .
- Ahora encuentre la ruta más larga con la diferencia leftDiff en el elemento secundario de la izquierda, digamos maxLen1 y la ruta más larga con la diferencia rightDiff en el elemento secundario de la derecha, digamos maxLen2 .
- Si leftDiff = (-1)*rightDiff , entonces ambas ramas del Node actual forman un AP, así que cambie ans al máximo del valor anterior de ans y maxLen1+maxLen2+1 .
- De lo contrario, cambie ans al máximo del valor anterior de ans , (maxLen1+1) y (maxLen2+1) , porque solo se puede seleccionar una de las dos rutas.
- Ahora devuelva maxLen1 y maxLen2 junto con la diferencia del AP del Node actual al Node principal.
- Imprimir ans después de que la función se detenga.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Tree Node
class Node {
public:
int data;
Node *left, *right;
Node(int d)
{
data = d;
left = right = NULL;
}
};
// Variable to store the maximum path length
int ans = 1;
// Function to find the maximum length
// of a path which forms an AP
vector<pair<int, int> > maxApPath(Node* root)
{
vector<pair<int, int> > l
= { { INT_MAX, 0 }, { INT_MAX, 0 } },
r = { { INT_MAX, 0 }, { INT_MAX, 0 } };
// Variables to store the difference with
// left and right nodes
int leftDiff = INT_MAX;
int rightDiff = INT_MAX;
// If left child exists
if (root->left) {
l = maxApPath(root->left);
leftDiff = (root->data)
- (root->left->data);
}
// If right child exists
if (root->right) {
r = maxApPath(root->right);
rightDiff = (root->data)
- (root->right->data);
}
// Variable to store the maximum length
// path in the left subtree in which
// the difference between each
// node is leftDiff
int maxLen1 = 0;
// Variable to store the maximum length
// path in the right subtree in which
// the difference between each
// node is rightDiff
int maxLen2 = 0;
// If a path having the difference
// leftDiff is found in left subtree
if (leftDiff == l[0].first
or l[0].first == INT_MAX) {
maxLen1 = l[0].second;
}
if (leftDiff == l[1].first
or l[1].first == INT_MAX) {
maxLen1 = max(maxLen1, l[1].second);
}
// If a path having the difference
// rightDiff is found in right subtree
if (rightDiff == r[0].first
or r[0].first == INT_MAX) {
maxLen2 = r[0].second;
}
if (rightDiff == r[1].first
or r[1].first == INT_MAX) {
maxLen2 = max(maxLen2, r[1].second);
}
// If both left and right subtree form AP
if (leftDiff == (-1 * rightDiff)) {
ans = max(ans, maxLen1 + maxLen2 + 1);
}
// Else
else {
ans = max({ ans, maxLen1 + 1,
maxLen2 + 1 });
}
// Return maximum path for
// leftDiff and rightDiff
return { { leftDiff, maxLen1 + 1 },
{ rightDiff, maxLen2 + 1 } };
}
// Driver Code
int main()
{
// Given Tree
Node* root = new Node(1);
root->left = new Node(8);
root->right = new Node(6);
root->left->left = new Node(6);
root->left->right = new Node(10);
root->right->left = new Node(3);
root->right->right = new Node(9);
root->left->left->right = new Node(4);
root->left->right->right = new Node(12);
root->right->right->right
= new Node(12);
root->left->left->right->right
= new Node(2);
root->right->right->right->left
= new Node(15);
root->right->right->right->right
= new Node(11);
maxApPath(root);
cout << ans;
return 0;
}
Java
// Java code for the above approach
class GFG{
// Tree Node
static class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
};
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Variable to store the maximum path length
static int ans = 1;
// Function to find the maximum length
// of a path which forms an AP
static pair[] maxApPath(Node root)
{
pair [] l
= { new pair(Integer.MAX_VALUE, 0 ), new pair( Integer.MAX_VALUE, 0 ) };
pair [] r = { new pair( Integer.MAX_VALUE, 0 ), new pair( Integer.MAX_VALUE, 0 ) };
// Variables to store the difference with
// left and right nodes
int leftDiff = Integer.MAX_VALUE;
int rightDiff = Integer.MAX_VALUE;
// If left child exists
if (root.left!=null) {
l = maxApPath(root.left);
leftDiff = (root.data)
- (root.left.data);
}
// If right child exists
if (root.right!=null) {
r = maxApPath(root.right);
rightDiff = (root.data)
- (root.right.data);
}
// Variable to store the maximum length
// path in the left subtree in which
// the difference between each
// node is leftDiff
int maxLen1 = 0;
// Variable to store the maximum length
// path in the right subtree in which
// the difference between each
// node is rightDiff
int maxLen2 = 0;
// If a path having the difference
// leftDiff is found in left subtree
if (leftDiff == l[0].first
|| l[0].first == Integer.MAX_VALUE) {
maxLen1 = l[0].second;
}
if (leftDiff == l[1].first
|| l[1].first == Integer.MAX_VALUE) {
maxLen1 = Math.max(maxLen1, l[1].second);
}
// If a path having the difference
// rightDiff is found in right subtree
if (rightDiff == r[0].first
|| r[0].first == Integer.MAX_VALUE) {
maxLen2 = r[0].second;
}
if (rightDiff == r[1].first
|| r[1].first == Integer.MAX_VALUE) {
maxLen2 = Math.max(maxLen2, r[1].second);
}
// If both left and right subtree form AP
if (leftDiff == (-1 * rightDiff)) {
ans = Math.max(ans, maxLen1 + maxLen2 + 1);
}
// Else
else {
ans = Math.max( Math.max(ans, maxLen1 + 1),
maxLen2 + 1 );
}
// Return maximum path for
// leftDiff and rightDiff
return new pair[] { new pair(leftDiff, maxLen1 + 1 ),
new pair( rightDiff, maxLen2 + 1 ) };
}
// Driver Code
public static void main(String[] args)
{
// Given Tree
Node root = new Node(1);
root.left = new Node(8);
root.right = new Node(6);
root.left.left = new Node(6);
root.left.right = new Node(10);
root.right.left = new Node(3);
root.right.right = new Node(9);
root.left.left.right = new Node(4);
root.left.right.right = new Node(12);
root.right.right.right
= new Node(12);
root.left.left.right.right
= new Node(2);
root.right.right.right.left
= new Node(15);
root.right.right.right.right
= new Node(11);
maxApPath(root);
System.out.print(ans);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach
# Tree Node
class Node:
def __init__(self, d):
self.data = d
self.left = self.right = None
# Variable to store the maximum path length
ans = 1;
# Function to find the maximum length
# of a path which forms an AP
def maxApPath(root):
l = [{ "first": 10 ** 9, "second": 0 }, { "first": 10 ** 9, "second": 0 }]
r = [{ "first": 10 ** 9, "second": 0 }, { "first": 10 ** 9, "second": 0 }];
# Variables to store the difference with
# left and right nodes
leftDiff = 10 ** 9;
rightDiff = 10 ** 9;
# If left child exists
if (root.left):
l = maxApPath(root.left);
leftDiff = (root.data) - (root.left.data);
# If right child exists
if (root.right) :
r = maxApPath(root.right);
rightDiff = (root.data) - (root.right.data);
# Variable to store the maximum length
# path in the left subtree in which
# the difference between each
# node is leftDiff
maxLen1 = 0;
# Variable to store the maximum length
# path in the right subtree in which
# the difference between each
# node is rightDiff
maxLen2 = 0;
# If a path having the difference
# leftDiff is found in left subtree
if (leftDiff == l[0]["first"] or l[0]["first"] == 10 ** 9):
maxLen1 = l[0]["second"];
if (leftDiff == l[1]["first"] or l[1]["first"] == 10 ** 9):
maxLen1 = max(maxLen1, l[1]["second"]);
# If a path having the difference
# rightDiff is found in right subtree
if (rightDiff == r[0]["first"] or r[0]["first"] == 10 ** 9):
maxLen2 = r[0]["second"];
if (rightDiff == r[1]["first"] or r[1]["first"] == 10 ** 9):
maxLen2 = max(maxLen2, r[1]["second"]);
global ans;
# If both left and right subtree form AP
if (leftDiff == (-1 * rightDiff)):
ans = max(ans, maxLen1 + maxLen2 + 1);
# Else
else:
ans = max(ans, max(maxLen1 + 1, maxLen2 + 1));
# Return maximum path for
# leftDiff and rightDiff
return [{ "first": leftDiff, "second": maxLen1 + 1 },
{ "first": rightDiff, "second": maxLen2 + 1 }];
# Driver Code
# Given Tree
root = Node(1);
root.left = Node(8);
root.right = Node(6);
root.left.left = Node(6);
root.left.right = Node(10);
root.right.left = Node(3);
root.right.right = Node(9);
root.left.left.right = Node(4);
root.left.right.right = Node(12);
root.right.right.right = Node(12);
root.left.left.right.right = Node(2);
root.right.right.right.left = Node(15);
root.right.right.right.right = Node(11);
maxApPath(root);
print(ans);
# This code is contributed by gfgking
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Tree Node
public class Node {
public int data;
public Node left, right;
public Node(int d) {
data = d;
left = right = null;
}
};
public class pair {
public int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Variable to store the maximum path length
static int ans = 1;
// Function to find the maximum length
// of a path which forms an AP
static pair[] maxApPath(Node root) {
pair[] l = { new pair(int.MaxValue, 0), new pair(int.MaxValue, 0) };
pair[] r = { new pair(int.MaxValue, 0), new pair(int.MaxValue, 0) };
// Variables to store the difference with
// left and right nodes
int leftDiff = int.MaxValue;
int rightDiff = int.MaxValue;
// If left child exists
if (root.left != null) {
l = maxApPath(root.left);
leftDiff = (root.data) - (root.left.data);
}
// If right child exists
if (root.right != null) {
r = maxApPath(root.right);
rightDiff = (root.data) - (root.right.data);
}
// Variable to store the maximum length
// path in the left subtree in which
// the difference between each
// node is leftDiff
int maxLen1 = 0;
// Variable to store the maximum length
// path in the right subtree in which
// the difference between each
// node is rightDiff
int maxLen2 = 0;
// If a path having the difference
// leftDiff is found in left subtree
if (leftDiff == l[0].first || l[0].first == int.MaxValue) {
maxLen1 = l[0].second;
}
if (leftDiff == l[1].first || l[1].first == int.MaxValue) {
maxLen1 = Math.Max(maxLen1, l[1].second);
}
// If a path having the difference
// rightDiff is found in right subtree
if (rightDiff == r[0].first || r[0].first == int.MaxValue) {
maxLen2 = r[0].second;
}
if (rightDiff == r[1].first || r[1].first == int.MaxValue) {
maxLen2 = Math.Max(maxLen2, r[1].second);
}
// If both left and right subtree form AP
if (leftDiff == (-1 * rightDiff)) {
ans = Math.Max(ans, maxLen1 + maxLen2 + 1);
}
// Else
else {
ans = Math.Max(Math.Max(ans, maxLen1 + 1), maxLen2 + 1);
}
// Return maximum path for
// leftDiff and rightDiff
return new pair[] { new pair(leftDiff, maxLen1 + 1), new pair(rightDiff, maxLen2 + 1) };
}
// Driver Code
public static void Main(String[] args) {
// Given Tree
Node root = new Node(1);
root.left = new Node(8);
root.right = new Node(6);
root.left.left = new Node(6);
root.left.right = new Node(10);
root.right.left = new Node(3);
root.right.right = new Node(9);
root.left.left.right = new Node(4);
root.left.right.right = new Node(12);
root.right.right.right = new Node(12);
root.left.left.right.right = new Node(2);
root.right.right.right.left = new Node(15);
root.right.right.right.right = new Node(11);
maxApPath(root);
Console.Write(ans);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
// Tree Node
class Node {
constructor(d) {
this.data = d;
this.left = this.right = null;
}
};
// Variable to store the maximum path length
let ans = 1;
// Function to find the maximum length
// of a path which forms an AP
function maxApPath(root) {
let l
= [{ first: Number.MAX_VALUE, second: 0 }, { first: Number.MAX_VALUE, second: 0 }],
r = [{ first: Number.MAX_VALUE, second: 0 }, { first: Number.MAX_VALUE, second: 0 }];
// Variables to store the difference with
// left and right nodes
let leftDiff = Number.MAX_VALUE;
let rightDiff = Number.MAX_VALUE;
// If left child exists
if (root.left) {
l = maxApPath(root.left);
leftDiff = (root.data)
- (root.left.data);
}
// If right child exists
if (root.right) {
r = maxApPath(root.right);
rightDiff = (root.data)
- (root.right.data);
}
// Variable to store the maximum length
// path in the left subtree in which
// the difference between each
// node is leftDiff
let maxLen1 = 0;
// Variable to store the maximum length
// path in the right subtree in which
// the difference between each
// node is rightDiff
let maxLen2 = 0;
// If a path having the difference
// leftDiff is found in left subtree
if (leftDiff == l[0].first
|| l[0].first == Number.MAX_VALUE) {
maxLen1 = l[0].second;
}
if (leftDiff == l[1].first
|| l[1].first == Number.MAX_VALUE) {
maxLen1 = Math.max(maxLen1, l[1].second);
}
// If a path having the difference
// rightDiff is found in right subtree
if (rightDiff == r[0].first
|| r[0].first == Number.MAX_VALUE) {
maxLen2 = r[0].second;
}
if (rightDiff == r[1].first
|| r[1].first == Number.MAX_VALUE) {
maxLen2 = Math.max(maxLen2, r[1].second);
}
// If both left and right subtree form AP
if (leftDiff == (-1 * rightDiff)) {
ans = Math.max(ans, maxLen1 + maxLen2 + 1);
}
// Else
else {
ans = Math.max(ans, Math.max(maxLen1 + 1,
maxLen2 + 1));
}
// Return maximum path for
// leftDiff and rightDiff
return [{ first: leftDiff, second: maxLen1 + 1 },
{ first: rightDiff, second: maxLen2 + 1 }];
}
// Driver Code
// Given Tree
let root = new Node(1);
root.left = new Node(8);
root.right = new Node(6);
root.left.left = new Node(6);
root.left.right = new Node(10);
root.right.left = new Node(3);
root.right.right = new Node(9);
root.left.left.right = new Node(4);
root.left.right.right = new Node(12);
root.right.right.right
= new Node(12);
root.left.left.right.right
= new Node(2);
root.right.right.right.left
= new Node(15);
root.right.right.right.right
= new Node(11);
maxApPath(root);
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
Producción:
6
Complejidad de tiempo: O(N) donde N es el número de Nodes en el
espacio auxiliar del árbol O(N)
Publicación traducida automáticamente
Artículo escrito por mashedpotat0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA