Solución al Problema ‘Cousins in Binary Tree II’

Descripción del Problema

El problema ‘Cousins in Binary Tree II’ plantea la necesidad de modificar un árbol binario de forma tal que cada nodo sea reemplazado por la suma de los valores de sus primos. Los primos en un árbol binario son aquellos nodos que se encuentran al mismo nivel pero tienen padres diferentes.

Enfoque de la Solución

Para resolver este problema, se deben seguir los siguientes pasos:

1. Realizar un recorrido nivel por nivel del árbol utilizando Breadth-First Search (BFS).
2. Calcular la suma de valores de los nodos primos para cada nivel.
3. Actualizar el valor de cada nodo con la suma correspondiente de sus primos.

Implementación en Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode replaceValueWithCousinsSum(TreeNode root) {
        if (root == null) return root;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            Map<TreeNode, Integer> parentSumMap = new HashMap<>();
            int totalSum = 0;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                // Adding children of current node to the queue
                if (node.left != null) {
                    queue.offer(node.left);
                    totalSum += node.left.val;
                    parentSumMap.put(node, parentSumMap.getOrDefault(node, 0) + node.left.val);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    totalSum += node.right.val;
                    parentSumMap.put(node, parentSumMap.getOrDefault(node, 0) + node.right.val);
                }
            }

            // Update value to sum of cousins
            for (TreeNode node : parentSumMap.keySet()) {
                if (node.left != null) {
                    node.left.val = totalSum - parentSumMap.get(node);
                }
                if (node.right != null) {
                    node.right.val = totalSum - parentSumMap.get(node);
                }
            }
        }
        root.val = 0; // The root node doesn't have cousins
        return root;
    }
}

La implementación en Java permite realizar un recorrido eficiente del árbol binario y actualizar los valores de los nodos conforme a sus primos. A continuación, se presenta el código Java que implementa la solución.

Conclusión

Modificar la estructura de un árbol binario para reflejar la suma de los valores de los primos de sus nodos es un ejercicio útil para fortalecer el conocimiento de algoritmos sobre estructuras complejas. El uso de Java es particularmente ventajoso dada su eficiencia en el manejo de estructuras de datos.