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.