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)