Ruta más larga con los mismos valores en un árbol binario

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.

Publicación traducida automáticamente

Artículo escrito por Pal13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *