Convierta un árbol binario arbitrario en un árbol que contenga la propiedad de suma de niños: conjunto 2

Pregunta: Hijos Suma Propiedad
de los hijos

             50

           / \     

         / \

       7 2

     / \ /\

   / \ / \

  3 5 1 30

Enfoque Ingenuo: El Enfoque Ingenuo se analiza en el Conjunto 1 de este artículo . Aquí, estamos discutiendo el enfoque optimizado.

Algoritmo: convierta los elementos secundarios al valor máximo posible, de modo que al retroceder no haya ningún elemento principal que tenga más valor que los elementos secundarios, por lo que no habrá una función adicional para atravesar nuevamente los subárboles desde ese Node.

• Si la suma de los hijos es menor que el Node actual, reemplace el valor de ambos hijos con el valor del Node actual.

if(Node->izquierda + Node->derecha <Node->datos) 
             poner Node->valor de datos tanto en el hijo

• Si la suma de los hijos es mayor o igual que el Node actual, reemplace el valor del Node actual con la suma de los hijos.

if(Node->izquierda->datos + Node->derecha->datos >= Node->datos) 
             coloque la suma de ambos valores de datos secundarios en Node->datos

• Mientras retrocede, sobrescriba los valores de Node existentes con la suma de los datos secundarios izquierdo y derecho.

(Nota: no habrá ningún caso en el que el valor del Node sea mayor que la suma de los valores de su hijo, porque les hemos dado el valor máximo posible).

Siga los pasos a continuación para resolver el problema:

• Si la raíz es nula , regrese.
• Inicialice la variable childSum como 0.
• Si root tiene hijos, agregue su valor a childSum.
• Si childSum es mayor que igual a root->data, establezca root->data como childSum .
• De lo contrario, si hay hijos de raíz, establezca los datos de sus hijos como raíz-> datos.
• Llame a la misma función para raíz->izquierda y raíz->derecha.
• Inicialice la variable totalSumToChangeParent como 0 .
• Si root tiene hijos, agregue el valor de sus datos a la variable totalSumToChangeParent.
• Si hay algún elemento secundario de root , establezca el valor de root como totalSumToChangeParent.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node in a binary tree
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int x)
    {
        data = x;
        left = NULL;
        right = NULL;
    }
};
 
// Convert the tree such that it holds
// children sum property
void convertTree(Node* root)
{
    if (root == NULL)
        return;
 
    // Calculating the sum
    // of left and right child
    int childSum = 0;
    if (root->left)
        childSum += root->left->data;
    if (root->right)
        childSum += root->right->data;
 
    // If sum of child is greater
    // then change the node's
    // data else change the data
    // of left and right child to
    // make sure they will get
    // the maximum possible value
    if (childSum >= root->data)
        root->data = childSum;
    else {
        if (root->left)
            root->left->data = root->data;
        if (root->right)
            root->right->data = root->data;
    }
 
    // Recursive call for left child
    convertTree(root->left);
 
    // Recursive call for right child
    convertTree(root->right);
 
    // Overwriting the parent's data
    int totalSumToChangeParent = 0;
    if (root->left)
        totalSumToChangeParent
            += root->left->data;
    if (root->right)
        totalSumToChangeParent
            += root->right->data;
    if (root->left || root->right)
        root->data = totalSumToChangeParent;
}
 
void printInorder(Node* root)
{
    if (root == NULL)
        return;
 
    // Recursive call to left child
    printInorder(root->left);
 
    // Printing the node's data
    cout << root->data << " ";
 
    // Recursive call to right child
    printInorder(root->right);
}
 
// Driver Code
int main()
{
 
    Node* root = new Node(50);
    root->left = new Node(7);
    root->right = new Node(2);
    root->left->left = new Node(3);
    root->left->right = new Node(5);
    root->right->left = new Node(1);
    root->right->right = new Node(30);
 
    convertTree(root);
 
    printInorder(root);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Structure of a node in a binary tree
static class Node {
    int data;
    Node left;
    Node right;
    Node(int x)
    {
        data = x;
        left = null;
        right = null;
    }
};
 
// Convert the tree such that it holds
// children sum property
static void convertTree(Node root)
{
    if (root == null)
        return;
 
    // Calculating the sum
    // of left and right child
    int childSum = 0;
    if (root.left!=null)
        childSum += root.left.data;
    if (root.right!=null)
        childSum += root.right.data;
 
    // If sum of child is greater
    // then change the node's
    // data else change the data
    // of left and right child to
    // make sure they will get
    // the maximum possible value
    if (childSum >= root.data)
        root.data = childSum;
    else {
        if (root.left!=null)
            root.left.data = root.data;
        if (root.right!=null)
            root.right.data = root.data;
    }
 
    // Recursive call for left child
    convertTree(root.left);
 
    // Recursive call for right child
    convertTree(root.right);
 
    // Overwriting the parent's data
    int totalSumToChangeParent = 0;
    if (root.left != null)
        totalSumToChangeParent
            += root.left.data;
    if (root.right != null)
        totalSumToChangeParent
            += root.right.data;
    if (root.left != null || root.right != null)
        root.data = totalSumToChangeParent;
}
 
static void printInorder(Node root)
{
    if (root == null)
        return;
 
    // Recursive call to left child
    printInorder(root.left);
 
    // Printing the node's data
    System.out.print(root.data+ " ");
 
    // Recursive call to right child
    printInorder(root.right);
}
 
// Driver Code
public static void main(String[] args)
{
 
    Node root = new Node(50);
    root.left = new Node(7);
    root.right = new Node(2);
    root.left.left = new Node(3);
    root.left.right = new Node(5);
    root.right.left = new Node(1);
    root.right.right = new Node(30);
 
    convertTree(root);
 
    printInorder(root);
}
}
 
// This code is contributed by 29AjayKumar

# Python code for the above approach
 
# Class of a node in a binary tree
class Node:
 
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
 
# Convert the tree such that it holds
# children sum property
def convertTree(root):
    if (root == None):
        return
 
    # Calculating the sum
    # of left and right child
    childSum = 0
    if (root.left):
        childSum += root.left.data
    if (root.right):
        childSum += root.right.data
 
    # If sum of child is greater
    # then change the node's
    # data else change the data
    # of left and right child to
    # make sure they will get
    # the maximum possible value
    if (childSum >= root.data):
        root.data = childSum
    else:
        if (root.left):
            root.left.data = root.data
        if (root.right):
            root.right.data = root.data
 
    # Recursive call for left child
    convertTree(root.left)
 
    # Recursive call for right child
    convertTree(root.right)
 
    # Overwriting the parent's data
    totalSumToChangeParent = 0
    if (root.left):
        totalSumToChangeParent += root.left.data
    if (root.right):
        totalSumToChangeParent += root.right.data
    if (root.left or root.right):
        root.data = totalSumToChangeParent
 
 
def printInorder(root):
    if (root == None):
        return
 
    # Recursive call to left child
    printInorder(root.left)
 
    # Printing the node's data
    print(root.data, end=" ")
 
    # Recursive call to right child
    printInorder(root.right)
 
# Driver Code
root = Node(50)
root.left = Node(7)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(5)
root.right.left = Node(1)
root.right.right = Node(30)
 
convertTree(root)
 
printInorder(root)
 
# self code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
public class GFG{
 
// Structure of a node in a binary tree
class Node {
    public int data;
    public Node left;
    public Node right;
    public Node(int x)
    {
        data = x;
        left = null;
        right = null;
    }
};
 
// Convert the tree such that it holds
// children sum property
static void convertTree(Node root)
{
    if (root == null)
        return;
 
    // Calculating the sum
    // of left and right child
    int childSum = 0;
    if (root.left!=null)
        childSum += root.left.data;
    if (root.right!=null)
        childSum += root.right.data;
 
    // If sum of child is greater
    // then change the node's
    // data else change the data
    // of left and right child to
    // make sure they will get
    // the maximum possible value
    if (childSum >= root.data)
        root.data = childSum;
    else {
        if (root.left!=null)
            root.left.data = root.data;
        if (root.right!=null)
            root.right.data = root.data;
    }
 
    // Recursive call for left child
    convertTree(root.left);
 
    // Recursive call for right child
    convertTree(root.right);
 
    // Overwriting the parent's data
    int totalSumToChangeParent = 0;
    if (root.left != null)
        totalSumToChangeParent
            += root.left.data;
    if (root.right != null)
        totalSumToChangeParent
            += root.right.data;
    if (root.left != null || root.right != null)
        root.data = totalSumToChangeParent;
}
 
static void printInorder(Node root)
{
    if (root == null)
        return;
 
    // Recursive call to left child
    printInorder(root.left);
 
    // Printing the node's data
    Console.Write(root.data+ " ");
 
    // Recursive call to right child
    printInorder(root.right);
}
 
// Driver Code
public static void Main(String[] args)
{
 
    Node root = new Node(50);
    root.left = new Node(7);
    root.right = new Node(2);
    root.left.left = new Node(3);
    root.left.right = new Node(5);
    root.right.left = new Node(1);
    root.right.right = new Node(30);
 
    convertTree(root);
 
    printInorder(root);
}
}
 
// This code is contributed by 29AjayKumar

<script>
       // JavaScript code for the above approach
 
       // Class of a node in a binary tree
       class Node {
 
           constructor(x) {
               this.data = x;
               this.left = null;
               this.right = null;
           }
       };
 
       // Convert the tree such that it holds
       // children sum property
       function convertTree(root) {
           if (root == null)
               return;
 
           // Calculating the sum
           // of left and right child
           let childSum = 0;
           if (root.left)
               childSum += root.left.data;
           if (root.right)
               childSum += root.right.data;
 
           // If sum of child is greater
           // then change the node's
           // data else change the data
           // of left and right child to
           // make sure they will get
           // the maximum possible value
           if (childSum >= root.data)
               root.data = childSum;
           else {
               if (root.left)
                   root.left.data = root.data;
               if (root.right)
                   root.right.data = root.data;
           }
 
           // Recursive call for left child
           convertTree(root.left);
 
           // Recursive call for right child
           convertTree(root.right);
 
           // Overwriting the parent's data
           let totalSumToChangeParent = 0;
           if (root.left)
               totalSumToChangeParent
                   += root.left.data;
           if (root.right)
               totalSumToChangeParent
                   += root.right.data;
           if (root.left || root.right)
               root.data = totalSumToChangeParent;
       }
 
       function printInorder(root) {
           if (root == null)
               return;
 
           // Recursive call to left child
           printInorder(root.left);
 
           // Printing the node's data
           document.write(root.data + " ");
 
           // Recursive call to right child
           printInorder(root.right);
       }
 
       // Driver Code
       let root = new Node(50);
       root.left = new Node(7);
       root.right = new Node(2);
       root.left.left = new Node(3);
       root.left.right = new Node(5);
       root.right.left = new Node(1);
       root.right.right = new Node(30);
 
       convertTree(root);
 
       printInorder(root);
 
 // This code is contributed by Potta Lokesh
   </script>

50 100 50 200 50 100 50

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)