Convierta un árbol binario de modo que cada Node almacene la suma de todos los Nodes en su subárbol derecho

Dado un árbol binario, cambie el valor de cada Node a la suma de todos los valores de los Nodes del subárbol derecho, incluido el suyo propio.
Ejemplos: 
 

Input : 
     1
   /   \
 2      3
Output : 
    4
  /   \
 2     3

Input : 
       1
      / \
     2   3
    / \   \
   4   5   6
Output :
       10
      / \
     7   9
    / \   \
   4   5   6

Enfoque : La idea es atravesar el árbol binario dado de abajo hacia arriba . Calcule recursivamente la suma de los Nodes en los subárboles derecho e izquierdo. Acumule la suma de los Nodes en el subárbol derecho al Node actual y devuelva la suma de los Nodes en el subárbol actual. 
A continuación se muestra la implementación del enfoque anterior. 
 

C++

// C++ program to store sum of nodes in
// right subtree in every node
#include <bits/stdc++.h>
using namespace std;
 
// Node of tree
struct Node {
    int data;
    Node *left, *right;
};
 
// Function to create a new node
struct Node* createNode(int item)
{
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
 
    return temp;
}
 
// Function to build new tree with
// all nodes having the sum of all
// nodes in its right subtree
int updateBTree(Node* root)
{
    // Base cases
    if (!root)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
 
    // Update right and left subtrees
    int rightsum = updateBTree(root->right);
    int leftsum = updateBTree(root->left);
 
    // Add rightsum to current node
    root->data += rightsum;
 
    // Return sum of values under root
    return root->data + leftsum;
}
 
// Function to traverse tree in inorder way
void inorder(struct Node* node)
{
    if (node == NULL)
        return;
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}
 
// Driver code
int main()
{
    /* Let us construct a binary tree
            1
           / \
          2   3
         / \   \
        4   5   6       */
    struct Node* root = NULL;
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
 
    // new tree construction
    updateBTree(root);
 
    cout << "Inorder traversal of the modified tree is \n";
    inorder(root);
 
    return 0;
}

Java

// Java program to store sum of nodes in
// right subtree in every node
class GFG
{
 
// Node of tree
static class Node
{
    int data;
    Node left, right;
};
 
// Function to create a new node
static Node createNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
 
// Function to build new tree with
// all nodes having the sum of all
// nodes in its right subtree
static int updateBTree(Node root)
{
    // Base cases
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return root.data;
 
    // Update right and left subtrees
    int rightsum = updateBTree(root.right);
    int leftsum = updateBTree(root.left);
 
    // Add rightsum to current node
    root.data += rightsum;
 
    // Return sum of values under root
    return root.data + leftsum;
}
 
// Function to traverse tree in inorder way
static void inorder( Node node)
{
    if (node == null)
        return;
    inorder(node.left);
    System.out.print( node.data + " ");
    inorder(node.right);
}
 
// Driver code
public static void main(String args[])
{
    /* Let us construct a binary tree
        1
        / \
        2 3
        / \ \
        4 5 6 */
    Node root = null;
    root = createNode(1);
    root.left = createNode(2);
    root.right = createNode(3);
    root.left.left = createNode(4);
    root.left.right = createNode(5);
    root.right.right = createNode(6);
 
    // new tree construction
    updateBTree(root);
 
    System.out.print( "Inorder traversal of the modified tree is \n");
    inorder(root);
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Program to convert expression tree
# from prefix expression
 
# Helper function that allocates a new
# node with the given data and None
# left and right pointers.                                
class createNode:
 
    # Construct to create a new node
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
         
# Function to build new tree with
# all nodes having the sum of all
# nodes in its right subtree
def updateBTree( root):
 
    # Base cases
    if (not root):
        return 0
    if (root.left == None and
        root.right == None):
        return root.data
 
    # Update right and left subtrees
    rightsum = updateBTree(root.right)
    leftsum = updateBTree(root.left)
 
    # Add rightsum to current node
    root.data += rightsum
 
    # Return sum of values under root
    return root.data + leftsum
 
# Function to traverse tree in inorder way
def inorder(node):
 
    if (node == None):
        return
    inorder(node.left)
    print(node.data, end = " ")
    inorder(node.right)
 
# Driver Code
if __name__ == '__main__':
     
    """ Let us convert binary tree
        1
    / \
    2 3
    / \ \
    4 5 6 """
    root = None
    root = createNode(1)
    root.left = createNode(2)
    root.right = createNode(3)
    root.left.left = createNode(4)
    root.left.right = createNode(5)
    root.right.right = createNode(6)
 
    # new tree construction
    updateBTree(root)
 
    print("Inorder traversal of the",
          "modified tree is")
    inorder(root)
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program to store sum of nodes in
// right subtree in every node
using System;
     
class GFG
{
 
// Node of tree
public class Node
{
    public int data;
    public Node left, right;
};
 
// Function to create a new node
static Node createNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
 
// Function to build new tree with
// all nodes having the sum of all
// nodes in its right subtree
static int updateBTree(Node root)
{
    // Base cases
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return root.data;
 
    // Update right and left subtrees
    int rightsum = updateBTree(root.right);
    int leftsum = updateBTree(root.left);
 
    // Add rightsum to current node
    root.data += rightsum;
 
    // Return sum of values under root
    return root.data + leftsum;
}
 
// Function to traverse tree in inorder way
static void inorder( Node node)
{
    if (node == null)
        return;
    inorder(node.left);
    Console.Write( node.data + " ");
    inorder(node.right);
}
 
// Driver code
public static void Main(String[] args)
{
    /* Let us construct a binary tree
        1
        / \
        2 3
        / \ \
        4 5 6 */
    Node root = null;
    root = createNode(1);
    root.left = createNode(2);
    root.right = createNode(3);
    root.left.left = createNode(4);
    root.left.right = createNode(5);
    root.right.right = createNode(6);
 
    // new tree construction
    updateBTree(root);
 
    Console.Write( "Inorder traversal of the modified tree is \n");
    inorder(root);
}
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
// Javascript program to store sum of nodes in
// right subtree in every node
 
 
// Node of tree
class Node
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Function to create a new node
function createNode(item)
{
    var temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
 
    return temp;
}
 
// Function to build new tree with
// all nodes having the sum of all
// nodes in its right subtree
function updateBTree(root)
{
 
    // Base cases
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return root.data;
 
    // Update right and left subtrees
    var rightsum = updateBTree(root.right);
    var leftsum = updateBTree(root.left);
 
    // Add rightsum to current node
    root.data += rightsum;
 
    // Return sum of values under root
    return root.data + leftsum;
}
 
// Function to traverse tree in inorder way
function inorder(node)
{
    if (node == null)
        return;
    inorder(node.left);
    document.write( node.data + " ");
    inorder(node.right);
}
 
// Driver code
/* Let us construct a binary tree
    1
    / \
    2 3
    / \ \
    4 5 6 */
var root = null;
root = createNode(1);
root.left = createNode(2);
root.right = createNode(3);
root.left.left = createNode(4);
root.left.right = createNode(5);
root.right.right = createNode(6);
 
// new tree construction
updateBTree(root);
document.write( "Inorder traversal of the modified tree is <br>");
inorder(root);
 
// This code is contributed by famously.
</script>
Producción: 

Inorder traversal of the modified tree is 
4 7 5 10 9 6

 

Complejidad de tiempo : O(n)
 

Publicación traducida automáticamente

Artículo escrito por akash1295 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 *