Dado un árbol binario, encuentre la longitud del camino más largo donde cada Node en el camino tiene el mismo valor. Esta ruta puede o no pasar por la raíz. La longitud del camino entre dos Nodes está representada por el número de aristas entre ellos.
Ejemplos:
Input :
2
/ \
7 2
/ \ \
1 1 2
Output : 2
Input :
4
/ \
4 4
/ \ \
4 9 5
Output : 3
La idea es recorrer recursivamente un árbol binario dado. Podemos pensar en cualquier camino (de Nodes con los mismos valores) en hasta dos direcciones (izquierda y derecha) desde su raíz. Entonces, para cada Node, queremos saber cuál es la longitud más larga posible que se extiende hacia la izquierda y la longitud más larga posible que se extiende hacia la derecha. La longitud más larga que se extiende desde el Node será 1 + longitud (Node->izquierda) si Node->izquierda existe y tiene el mismo valor que Node. De manera similar para el caso del Node->derecho.
Mientras calculamos las longitudes, cada respuesta candidata será la suma de las longitudes en ambas direcciones desde ese Node. Seguimos actualizando estas respuestas y devolvemos la máxima.
C++
// C++ program to find the length of longest
// path with same values in a binary tree.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int val;
struct Node *left, *right;
};
/* Function to print the longest path
of same values */
int length(Node *node, int *ans) {
if (!node)
return 0;
// Recursive calls to check for subtrees
int left = length(node->left, ans);
int right = length(node->right, ans);
// Variables to store maximum lengths in two directions
int Leftmax = 0, Rightmax = 0;
// If curr node and it's left child has same value
if (node->left && node->left->val == node->val)
Leftmax += left + 1;
// If curr node and it's right child has same value
if (node->right && node->right->val == node->val)
Rightmax += right + 1;
*ans = max(*ans, Leftmax + Rightmax);
return max(Leftmax, Rightmax);
}
/* Driver function to find length of
longest same value path*/
int longestSameValuePath(Node *root) {
int ans = 0;
length(root, &ans);
return ans;
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
Node *newNode(int data) {
Node *temp = new Node;
temp->val = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver code
int main() {
/* Let us construct a Binary Tree
4
/ \
4 4
/ \ \
4 9 5 */
Node *root = NULL;
root = newNode(4);
root->left = newNode(4);
root->right = newNode(4);
root->left->left = newNode(4);
root->left->right = newNode(9);
root->right->right = newNode(5);
cout << longestSameValuePath(root);
return 0;
}
Java
// Java program to find the length of longest
// path with same values in a binary tree.
class GFG
{
static int ans;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static class Node
{
int val;
Node left, right;
};
/* Function to print the longest path
of same values */
static int length(Node node)
{
if (node == null)
return 0;
// Recursive calls to check for subtrees
int left = length(node.left);
int right = length(node.right);
// Variables to store maximum lengths
// in two directions
int Leftmax = 0, Rightmax = 0;
// If curr node and it's left child
// has same value
if (node.left != null &&
node.left.val == node.val)
Leftmax += left + 1;
// If curr node and it's right child
// has same value
if (node.right != null &&
node.right.val == node.val)
Rightmax += right + 1;
ans = Math.max(ans, Leftmax + Rightmax);
return Math.max(Leftmax, Rightmax);
}
// Function to find length of
// longest same value path
static int longestSameValuePath(Node root)
{
ans = 0;
length(root);
return ans;
}
/* Helper function that allocates a
new node with the given data and
null left and right pointers. */
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void main(String[] args)
{
/* Let us construct a Binary Tree
4
/ \
4 4
/ \ \
4 9 5 */
Node root = null;
root = newNode(4);
root.left = newNode(4);
root.right = newNode(4);
root.left.left = newNode(4);
root.left.right = newNode(9);
root.right.right = newNode(5);
System.out.print(longestSameValuePath(root));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find the length of longest # path with same values in a binary tree. # Helper function that allocates a # new node with the given data and # None left and right pointers. class newNode: def __init__(self, data): self.val = data self.left = self.right = None # Function to print the longest path # of same values def length(node, ans): if (not node): return 0 # Recursive calls to check for subtrees left = length(node.left, ans) right = length(node.right, ans) # Variables to store maximum lengths # in two directions Leftmax = 0 Rightmax = 0 # If curr node and it's left child has same value if (node.left and node.left.val == node.val): Leftmax += left + 1 # If curr node and it's right child has same value if (node.right and node.right.val == node.val): Rightmax += right + 1 ans[0] = max(ans[0], Leftmax + Rightmax) return max(Leftmax, Rightmax) # Driver function to find length of # longest same value path def longestSameValuePath(root): ans = [0] length(root, ans) return ans[0] # Driver code if __name__ == '__main__': # Let us construct a Binary Tree # 4 # / \ # 4 4 # / \ \ # 4 9 5 root = None root = newNode(4) root.left = newNode(4) root.right = newNode(4) root.left.left = newNode(4) root.left.right = newNode(9) root.right.right = newNode(5) print(longestSameValuePath(root)) # This code is contributed by PranchalK
C#
// C# program to find the length of longest
// path with same values in a binary tree.
using System;
class GFG
{
static int ans;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
public class Node
{
public int val;
public Node left, right;
};
/* Function to print the longest path
of same values */
static int length(Node node)
{
if (node == null)
return 0;
// Recursive calls to check for subtrees
int left = length(node.left);
int right = length(node.right);
// Variables to store maximum lengths
// in two directions
int Leftmax = 0, Rightmax = 0;
// If curr node and it's left child
// has same value
if (node.left != null &&
node.left.val == node.val)
Leftmax += left + 1;
// If curr node and it's right child
// has same value
if (node.right != null &&
node.right.val == node.val)
Rightmax += right + 1;
ans = Math.Max(ans, Leftmax + Rightmax);
return Math.Max(Leftmax, Rightmax);
}
// Function to find length of
// longest same value path
static int longestSameValuePath(Node root)
{
ans = 0;
length(root);
return ans;
}
/* Helper function that allocates a
new node with the given data and
null left and right pointers. */
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void Main(String[] args)
{
/* Let us construct a Binary Tree
4
/ \
4 4
/ \ \
4 9 5 */
Node root = null;
root = newNode(4);
root.left = newNode(4);
root.right = newNode(4);
root.left.left = newNode(4);
root.left.right = newNode(9);
root.right.right = newNode(5);
Console.Write(longestSameValuePath(root));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find the length of longest
// path with same values in a binary tree.
let ans;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.val = data;
}
}
/* Function to print the longest path
of same values */
function length(node)
{
if (node == null)
return 0;
// Recursive calls to check for subtrees
let left = length(node.left);
let right = length(node.right);
// Variables to store maximum lengths
// in two directions
let Leftmax = 0, Rightmax = 0;
// If curr node and it's left child
// has same value
if (node.left != null &&
node.left.val == node.val)
Leftmax += left + 1;
// If curr node and it's right child
// has same value
if (node.right != null &&
node.right.val == node.val)
Rightmax += right + 1;
ans = Math.max(ans, Leftmax + Rightmax);
return Math.max(Leftmax, Rightmax);
}
// Function to find length of
// longest same value path
function longestSameValuePath(root)
{
ans = 0;
length(root);
return ans;
}
/* Helper function that allocates a
new node with the given data and
null left and right pointers. */
function newNode(data)
{
let temp = new Node(data);
temp.val = data;
temp.left = temp.right = null;
return temp;
}
/* Let us construct a Binary Tree
4
/ \
4 4
/ \ \
4 9 5 */
let root = null;
root = newNode(4);
root.left = newNode(4);
root.right = newNode(4);
root.left.left = newNode(4);
root.left.right = newNode(9);
root.right.right = newNode(5);
document.write(longestSameValuePath(root));
</script>
Producción:
3
Análisis de Complejidad:
- Complejidad de tiempo: O(n), donde n es el número de Nodes en el árbol, ya que cada Node se procesa una vez.
- Espacio Auxiliar: O(h), donde h es la altura del árbol ya que la recursividad puede llegar hasta la profundidad h.