给定一棵二叉树，将每个节点中的值更改为右子树（包括其自身子树）中节点中所有值的总和。 例如：
null
Input : 1 / 2 3Output : 4 / 2 3Input : 1 / 2 3 / 4 5 6Output : 10 / 7 9 / 4 5 6
方法 ：这个想法是遍历给定的二叉树 自下而上 方式递归计算左右子树中的节点之和。将右子树中的节点之和累加到当前节点，并返回当前子树下的节点之和。 下面是上述方法的实现。
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 " ; 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 conion updateBTree(root); System.out.print( "Inorder traversal of the modified tree is " ); 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 poers. class createNode: # Conto 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 conion updateBTree(root); Console.Write( "Inorder traversal of the modified tree is " ); 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 conion updateBTree(root); document.write( "Inorder traversal of the modified tree is <br>" ); inorder(root); // This code is contributed by famously. </script> |
输出：
Inorder traversal of the modified tree is 4 7 5 10 9 6
时间复杂性 ：O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
