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)