Dado un árbol binario que consta de N Nodes, la tarea es encontrar la longitud del camino más largo desde cualquier Node hasta la parte inferior del árbol de manera que todos los valores de los Nodes formen una progresión aritmética .
Ejemplos:
Aporte:
Salida: 4
Explicación:
Del árbol anterior, la ruta más larga con valores de Node que forman un AP es {6, 9, 12, 15} (Longitud = 4).Aporte:
Salida: 2
Enfoque: El problema dado se puede resolver usando la recursividad y realizando el DFS Traversal en el árbol dado . La idea es realizar un seguimiento de la diferencia entre el Node raíz actual y el siguiente Node descendiente y actualizar la longitud de la ruta más larga en consecuencia. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos maxLength como 1 que almacene la longitud máxima de la ruta desde cualquier Node hasta la parte inferior del árbol formando una progresión aritmética.
- Defina una función , digamos dfs(root, currentDifference, count, maxLength) que tome el Node raíz actual, la diferencia actual, el conteo de Nodes que forman AP y la longitud máxima resultante como parámetro y realice los siguientes pasos:
- Si existe el Node izquierdo de la raíz, realice los siguientes pasos:
- Encuentra la diferencia entre el valor de la raíz y su Node izquierdo.
- Si se encuentra que la diferencia es currentDifference , entonces actualice el valor de maxLength al máximo de maxLength y (count + 1) y llame recursivamente a la función dfs(root->left, currentDifference, count + 1, maxLength) .
- De lo contrario, llame recursivamente a dfs(root->left, difference, 2, maxLength) .
- Si existe el Node derecho de la raíz, realice los siguientes pasos:
- Encuentra la diferencia entre el valor de la raíz y su Node derecho.
- Si se encuentra que la diferencia es currentDifference , actualice el valor de maxLength al máximo de maxLength y (count + 1) y llame recursivamente a la función dfs(root->right, currentDifference, count + 1, maxLength) .
- De lo contrario, llame recursivamente a dfs(root->left, difference, 2, maxLength) .
- Si existe el Node izquierdo de la raíz, realice los siguientes pasos:
- Si el hijo izquierdo del Node raíz dado existe, llame a dfs(root->left, difference, 2, maxLength) donde la diferencia es la diferencia entre el valor de la raíz y su Node izquierdo.
- Si existe el hijo derecho del Node raíz dado, llame a dfs(root->right, difference, 2, maxLength) donde la diferencia es la diferencia entre el valor de la raíz y su Node derecho.
- Después de completar los pasos anteriores, imprima el valor de maxLength como la longitud máxima resultante de la ruta desde cualquier Node hasta la parte inferior del árbol formando una progresión aritmética .
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;
// Structure of the Tree Node
struct Tree {
int val;
Tree *left, *right;
};
// Function to create a new node
Tree* newNode(int data)
{
Tree* temp = new Tree();
temp->val = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to perform DFS Traversal
// to find the maximum length of a path
// to a bottom node forming an AP
void dfs(Tree* root, int currentDifference,
int count, int& maxLength)
{
// If the root's left child exists
if (root->left) {
// Calculate the difference
int difference = root->left->val
- root->val;
// If the difference is same
// as the current difference
if (difference == currentDifference) {
dfs(root->left, currentDifference,
count + 1, maxLength);
// Update the maxLength
maxLength = max(maxLength,
count + 1);
}
// Otherwise
else {
dfs(root->left, difference,
2, maxLength);
}
}
// If the root's right child exists
if (root->right) {
// Find the difference
int difference = root->right->val
- root->val;
// If the difference is the same
// as the current difference
if (difference == currentDifference) {
dfs(root->right, currentDifference,
count + 1, maxLength);
// Update the maxLength
maxLength = max(maxLength,
count + 1);
}
// Otherwise
else {
dfs(root->right, difference,
2, maxLength);
}
}
}
// Function to find the maximum length
// of the path from any node to bottom
// of the tree forming an AP
int maximumLengthAP(Tree* root)
{
// Base Cases
if (root == NULL)
return 0;
if (root->left == NULL
and root->right == NULL) {
return 1;
}
// Stores the resultant
// maximum length of the path
int maxLength = 2;
// If the root's left child exists
if (root->left) {
int difference = root->left->val
- root->val;
dfs(root->left, difference, 2,
maxLength);
}
// If the root's right child exists
if (root->right) {
int difference = root->right->val
- root->val;
dfs(root->right, difference, 2,
maxLength);
}
// Return the maximum length obtained
return maxLength;
}
// Driver Code
int main()
{
// Given Tree
Tree* root = newNode(6);
root->right = newNode(9);
root->right->left = newNode(7);
root->right->right = newNode(12);
root->right->right->right = newNode(15);
cout << maximumLengthAP(root);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
static int maxLength;
// TreeNode class
static class Node
{
public int val;
public Node left, right;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.val = key;
temp.left = temp.right = null;
return temp;
}
// Function to perform DFS Traversal
// to find the maximum length of a path
// to a bottom node forming an AP
static void dfs(Node root, int currentDifference,
int count)
{
// If the root's left child exists
if (root.left != null)
{
// Calculate the difference
int difference = root.left.val - root.val;
// If the difference is same
// as the current difference
if (difference == currentDifference)
{
dfs(root.left, currentDifference,
count + 1);
// Update the maxLength
maxLength = Math.max(maxLength,
count + 1);
}
// Otherwise
else
{
dfs(root.left, difference, 2);
}
}
// If the root's right child exists
if (root.right != null)
{
// Find the difference
int difference = root.right.val - root.val;
// If the difference is the same
// as the current difference
if (difference == currentDifference)
{
dfs(root.right, currentDifference,
count + 1);
// Update the maxLength
maxLength = Math.max(maxLength,
count + 1);
}
// Otherwise
else
{
dfs(root.right, difference, 2);
}
}
}
// Function to find the maximum length
// of the path from any node to bottom
// of the tree forming an AP
static int maximumLengthAP(Node root)
{
// Base Cases
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
{
return 1;
}
// Stores the resultant
// maximum length of the path
maxLength = 2;
// If the root's left child exists
if (root.left != null)
{
int difference = root.left.val - root.val;
dfs(root.left, difference, 2);
}
// If the root's right child exists
if (root.right != null)
{
int difference = root.right.val - root.val;
dfs(root.right, difference, 2);
}
// Return the maximum length obtained
return maxLength;
}
// Driver code
public static void main(String[] args)
{
// Given Tree
Node root = newNode(6);
root.right = newNode(9);
root.right.left = newNode(7);
root.right.right = newNode(12);
root.right.right.right = newNode(15);
System.out.println(maximumLengthAP(root));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach maxLength = 2 class Node: # Constructor to set the data of # the newly created tree node def __init__(self, key): self.val = key self.left = None self.right = None # Function to perform DFS Traversal # to find the maximum length of a path # to a bottom node forming an AP def dfs(root, currentDifference, count): global maxLength # If the root's left child exists if (root.left != None): # Calculate the difference difference = root.left.val - root.val # If the difference is same # as the current difference if (difference == currentDifference): dfs(root.left, currentDifference, count + 1) # Update the maxLength maxLength = max(maxLength, count + 1) # Otherwise else: dfs(root.left, difference, 2) # If the root's right child exists if (root.right != None): # Find the difference difference = root.right.val - root.val # If the difference is the same # as the current difference if (difference == currentDifference): dfs(root.right, currentDifference, count + 1) # Update the maxLength maxLength = max(maxLength, count + 1) # Otherwise else: dfs(root.right, difference, 2) # Function to find the maximum length # of the path from any node to bottom # of the tree forming an AP def maximumLengthAP(root): global maxLength # Base Cases if (root == None): return 0 if (root.left == None and root.right == None): return 1 # If the root's left child exists if (root.left != None): difference = root.left.val - root.val dfs(root.left, difference, 2) # If the root's right child exists if (root.right != None): difference = root.right.val - root.val dfs(root.right, difference, 2) # Return the maximum length obtained return maxLength # Given Tree root = Node(6) root.right = Node(9) root.right.left = Node(7) root.right.right = Node(12) root.right.right.right = Node(15) print(maximumLengthAP(root)) # This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
class GFG{
static int maxLength;
// TreeNode class
class Node
{
public int val;
public Node left, right;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.val = key;
temp.left = temp.right = null;
return temp;
}
// Function to perform DFS Traversal
// to find the maximum length of a path
// to a bottom node forming an AP
static void dfs(Node root, int currentDifference,
int count)
{
// If the root's left child exists
if (root.left != null)
{
// Calculate the difference
int difference = root.left.val - root.val;
// If the difference is same
// as the current difference
if (difference == currentDifference)
{
dfs(root.left, currentDifference,
count + 1);
// Update the maxLength
maxLength = Math.Max(maxLength,
count + 1);
}
// Otherwise
else
{
dfs(root.left, difference, 2);
}
}
// If the root's right child exists
if (root.right != null)
{
// Find the difference
int difference = root.right.val - root.val;
// If the difference is the same
// as the current difference
if (difference == currentDifference)
{
dfs(root.right, currentDifference,
count + 1);
// Update the maxLength
maxLength = Math.Max(maxLength,
count + 1);
}
// Otherwise
else
{
dfs(root.right, difference, 2);
}
}
}
// Function to find the maximum length
// of the path from any node to bottom
// of the tree forming an AP
static int maximumLengthAP(Node root)
{
// Base Cases
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
{
return 1;
}
// Stores the resultant
// maximum length of the path
maxLength = 2;
// If the root's left child exists
if (root.left != null)
{
int difference = root.left.val - root.val;
dfs(root.left, difference, 2);
}
// If the root's right child exists
if (root.right != null)
{
int difference = root.right.val - root.val;
dfs(root.right, difference, 2);
}
// Return the maximum length obtained
return maxLength;
}
// Driver code
public static void Main(String[] args)
{
// Given Tree
Node root = newNode(6);
root.right = newNode(9);
root.right.left = newNode(7);
root.right.right = newNode(12);
root.right.right.right = newNode(15);
Console.WriteLine(maximumLengthAP(root));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
let maxLength;
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.val = key;
}
}
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Function to perform DFS Traversal
// to find the maximum length of a path
// to a bottom node forming an AP
function dfs(root, currentDifference, count)
{
// If the root's left child exists
if (root.left != null)
{
// Calculate the difference
let difference = root.left.val - root.val;
// If the difference is same
// as the current difference
if (difference == currentDifference)
{
dfs(root.left, currentDifference,
count + 1);
// Update the maxLength
maxLength = Math.max(maxLength,
count + 1);
}
// Otherwise
else
{
dfs(root.left, difference, 2);
}
}
// If the root's right child exists
if (root.right != null)
{
// Find the difference
let difference = root.right.val - root.val;
// If the difference is the same
// as the current difference
if (difference == currentDifference)
{
dfs(root.right, currentDifference,
count + 1);
// Update the maxLength
maxLength = Math.max(maxLength,
count + 1);
}
// Otherwise
else
{
dfs(root.right, difference, 2);
}
}
}
// Function to find the maximum length
// of the path from any node to bottom
// of the tree forming an AP
function maximumLengthAP(root)
{
// Base Cases
if (root == null)
return 0;
if (root.left == null &&
root.right == null)
{
return 1;
}
// Stores the resultant
// maximum length of the path
maxLength = 2;
// If the root's left child exists
if (root.left != null)
{
let difference = root.left.val - root.val;
dfs(root.left, difference, 2);
}
// If the root's right child exists
if (root.right != null)
{
let difference = root.right.val - root.val;
dfs(root.right, difference, 2);
}
// Return the maximum length obtained
return maxLength;
}
// Given Tree
let root = newNode(6);
root.right = newNode(9);
root.right.left = newNode(7);
root.right.right = newNode(12);
root.right.right.right = newNode(15);
document.write(maximumLengthAP(root));
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA