问题: 给定一个任意的二叉树，将其转换为一个包含 子女是财产的总和 。只能增加任何节点中的数据值（不能更改树的结构，也不能减少任何节点的值）。 例如，下面的树不包含children sum属性，请将其转换为包含该属性的树。
null
50 / / 7 2 / / / / 3 5 1 30
算法： 按post顺序遍历给定的树以进行转换，即首先更改左和右子级以保留children sum属性，然后更改父节点。 让节点的数据和子节点的总和之间的差异是不同的。
diff = node’s children sum - node’s data
如果diff为0，则无需执行任何操作。 如果diff>0（节点的数据小于节点的子节点和），则按diff递增节点的数据。 如果diff<0（节点的数据大于节点的子节点和），则增加一个子节点的数据。如果left或right child都不为NULL，我们可以选择递增。让我们总是先增加左边的孩子。增加一个子树的值会改变子树的childrensum属性，所以我们也需要改变左子树。所以我们递归地增加左边的子项。如果left child为空，那么我们递归地为right child调用increment（）。 让我们运行给定示例的算法。 首先转换左子树（增量7到8）。
50 / / 8 2 / / / / 3 5 1 30
然后转换右子树（增量2到31）
50 / / 8 31 / / / / 3 5 1 30
现在转换根，我们必须增加左子树来转换根。
50 / / 19 31 / / / / 14 5 1 30
请注意最后一步——我们将8增加到19，为了修复子树，我们将3增加到14。 实施：
C++
/* C++ Program to convert an aribitary binary tree to a tree that hold children sum property */ #include<bits/stdc++.h> using namespace std; class node { public : int data; node* left; node* right; /* Constructor that allocates a new node with the given data and NULL left and right pointers. */ node( int data) { this ->data = data; this ->left = NULL; this ->right = NULL; } }; /* This function is used to increment left subtree */ void increment(node* node, int diff); /* This function changes a tree to hold children sum property */ void convertTree(node* node) { int left_data = 0, right_data = 0, diff; /* If tree is empty or it's a leaf node then return true */ if (node == NULL || (node->left == NULL && node->right == NULL)) return ; else { /* convert left and right subtrees */ convertTree(node->left); convertTree(node->right); /* If left child is not present then 0 is used as data of left child */ if (node->left != NULL) left_data = node->left->data; /* If right child is not present then 0 is used as data of right child */ if (node->right != NULL) right_data = node->right->data; /* get the diff of node's data and children sum */ diff = left_data + right_data - node->data; /* If node's children sum is greater than the node's data */ if (diff > 0) node->data = node->data + diff; /* THIS IS TRICKY --> If node's data is greater than children sum, then increment subtree by diff */ if (diff < 0) increment(node, -diff); // -diff is used to make diff positive } } /* This function is used to increment subtree by diff */ void increment(node* node, int diff) { /* IF left child is not NULL then increment it */ if (node->left != NULL) { node->left->data = node->left->data + diff; // Recursively call to fix // the descendants of node->left increment(node->left, diff); } else if (node->right != NULL) // Else increment right child { node->right->data = node->right->data + diff; // Recursively call to fix // the descendants of node->right increment(node->right, diff); } } /* Given a binary tree, printInorder() prints out its inorder traversal*/ void printInorder(node* node) { if (node == NULL) return ; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ cout<<node->data<< " " ; /* now recur on right child */ printInorder(node->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); cout << "Inorder traversal before conversion: " << endl; printInorder(root); convertTree(root); cout << "Inorder traversal after conversion: " << endl; printInorder(root); return 0; } // This code is contributed by rathbhupendra |
C
/* Program to convert an aribitary binary tree to a tree that holds children sum property */ #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* left; struct node* right; }; /* This function is used to increment left subtree */ void increment( struct node* node, int diff); /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data); /* This function changes a tree to hold children sum property */ void convertTree( struct node* node) { int left_data = 0, right_data = 0, diff; /* If tree is empty or it's a leaf node then return true */ if (node == NULL || (node->left == NULL && node->right == NULL)) return ; else { /* convert left and right subtrees */ convertTree(node->left); convertTree(node->right); /* If left child is not present then 0 is used as data of left child */ if (node->left != NULL) left_data = node->left->data; /* If right child is not present then 0 is used as data of right child */ if (node->right != NULL) right_data = node->right->data; /* get the diff of node's data and children sum */ diff = left_data + right_data - node->data; /* If node's children sum is greater than the node's data */ if (diff > 0) node->data = node->data + diff; /* THIS IS TRICKY --> If node's data is greater than children sum, then increment subtree by diff */ if (diff < 0) increment(node, -diff); // -diff is used to make diff positive } } /* This function is used to increment subtree by diff */ void increment( struct node* node, int diff) { /* IF left child is not NULL then increment it */ if (node->left != NULL) { node->left->data = node->left->data + diff; // Recursively call to fix the descendants of node->left increment(node->left, diff); } else if (node->right != NULL) // Else increment right child { node->right->data = node->right->data + diff; // Recursively call to fix the descendants of node->right increment(node->right, diff); } } /* Given a binary tree, printInorder() prints out its inorder traversal*/ void printInorder( struct node* node) { if (node == NULL) return ; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ printf ( "%d " , node->data); /* now recur on right child */ printInorder(node->right); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } /* Driver program to test above functions */ int main() { struct node *root = newNode(50); root->left = newNode(7); root->right = newNode(2); root->left->left = newNode(3); root->left->right = newNode(5); root->right->left = newNode(1); root->right->right = newNode(30); printf ( " Inorder traversal before conversion " ); printInorder(root); convertTree(root); printf ( " Inorder traversal after conversion " ); printInorder(root); getchar (); return 0; } |
JAVA
// Java program to convert an arbitrary binary tree to a tree that holds // children sum property // A binary tree node class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; /* This function changes a tree to hold children sum property */ void convertTree(Node node) { int left_data = 0 , right_data = 0 , diff; /* If tree is empty or it's a leaf node then return true */ if (node == null || (node.left == null && node.right == null )) return ; else { /* convert left and right subtrees */ convertTree(node.left); convertTree(node.right); /* If left child is not present then 0 is used as data of left child */ if (node.left != null ) left_data = node.left.data; /* If right child is not present then 0 is used as data of right child */ if (node.right != null ) right_data = node.right.data; /* get the diff of node's data and children sum */ diff = left_data + right_data - node.data; /* If node's children sum is greater than the node's data */ if (diff > 0 ) node.data = node.data + diff; /* THIS IS TRICKY --> If node's data is greater than children sum, then increment subtree by diff */ if (diff < 0 ) // -diff is used to make diff positive increment(node, -diff); } } /* This function is used to increment subtree by diff */ void increment(Node node, int diff) { /* IF left child is not NULL then increment it */ if (node.left != null ) { node.left.data = node.left.data + diff; // Recursively call to fix the descendants of node->left increment(node.left, diff); } else if (node.right != null ) // Else increment right child { node.right.data = node.right.data + diff; // Recursively call to fix the descendants of node->right increment(node.right, diff); } } /* Given a binary tree, printInorder() prints out its inorder traversal*/ void printInorder(Node node) { if (node == null ) return ; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ System.out.print(node.data + " " ); /* now recur on right child */ printInorder(node.right); } // Driver program to test above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 50 ); tree.root.left = new Node( 7 ); tree.root.right = new Node( 2 ); tree.root.left.left = new Node( 3 ); tree.root.left.right = new Node( 5 ); tree.root.right.left = new Node( 1 ); tree.root.right.right = new Node( 30 ); System.out.println( "Inorder traversal before conversion is :" ); tree.printInorder(tree.root); tree.convertTree(tree.root); System.out.println( "" ); System.out.println( "Inorder traversal after conversion is :" ); tree.printInorder(tree.root); } } // This code has been contributed by Mayank Jaiswal(mayank_24) |
Python3
# Program to convert an aribitary binary tree # to a tree that holds children sum property # Helper function that allocates a new # node with the given data and None # left and right poers. class newNode: # Construct to create a new node def __init__( self , key): self .data = key self .left = None self .right = None # This function changes a tree to # hold children sum property def convertTree(node): left_data = 0 right_data = 0 diff = 0 # If tree is empty or it's a # leaf node then return true if (node = = None or (node.left = = None and node.right = = None )): return else : """ convert left and right subtrees """ convertTree(node.left) convertTree(node.right) """ If left child is not present then 0 is used as data of left child """ if (node.left ! = None ): left_data = node.left.data """ If right child is not present then 0 is used as data of right child """ if (node.right ! = None ): right_data = node.right.data """ get the diff of node's data and children sum """ diff = left_data + right_data - node.data """ If node's children sum is greater than the node's data """ if (diff > 0 ): node.data = node.data + diff """ THIS IS TRICKY -. If node's data is greater than children sum, then increment subtree by diff """ if (diff < 0 ): increment(node, - diff) # -diff is used to # make diff positive """ This function is used to increment subtree by diff """ def increment(node, diff): """ IF left child is not None then increment it """ if (node.left ! = None ): node.left.data = node.left.data + diff # Recursively call to fix the # descendants of node.left increment(node.left, diff) elif (node.right ! = None ): # Else increment right child node.right.data = node.right.data + diff # Recursively call to fix the # descendants of node.right increment(node.right, diff) """ Given a binary tree, printInorder() prints out its inorder traversal""" def printInorder(node): if (node = = None ): return """ first recur on left child """ printInorder(node.left) """ then print the data of node """ print (node.data,end = " " ) """ now recur on right child """ printInorder(node.right) # Driver Code if __name__ = = '__main__' : root = newNode( 50 ) root.left = newNode( 7 ) root.right = newNode( 2 ) root.left.left = newNode( 3 ) root.left.right = newNode( 5 ) root.right.left = newNode( 1 ) root.right.right = newNode( 30 ) print ( "Inorder traversal before conversion" ) printInorder(root) convertTree(root) print ( "Inorder traversal after conversion " ) printInorder(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to convert an arbitrary // binary tree to a tree that holds // children sum property using System; // A binary tree node public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } class GFG { public Node root; /* This function changes a tree to hold children sum property */ public virtual void convertTree(Node node) { int left_data = 0, right_data = 0, diff; /* If tree is empty or it's a leaf node then return true */ if (node == null || (node.left == null && node.right == null )) { return ; } else { /* convert left and right subtrees */ convertTree(node.left); convertTree(node.right); /* If left child is not present then 0 is used as data of left child */ if (node.left != null ) { left_data = node.left.data; } /* If right child is not present then 0 is used as data of right child */ if (node.right != null ) { right_data = node.right.data; } /* get the diff of node's data and children sum */ diff = left_data + right_data - node.data; /* If node's children sum is greater than the node's data */ if (diff > 0) { node.data = node.data + diff; } /* THIS IS TRICKY --> If node's data is greater than children sum, then increment subtree by diff */ if (diff < 0) { // -diff is used to make diff positive increment(node, -diff); } } } /* This function is used to increment subtree by diff */ public virtual void increment(Node node, int diff) { /* IF left child is not NULL then increment it */ if (node.left != null ) { node.left.data = node.left.data + diff; // Recursively call to fix the // descendants of node->left increment(node.left, diff); } else if (node.right != null ) // Else increment right child { node.right.data = node.right.data + diff; // Recursively call to fix the // descendants of node->right increment(node.right, diff); } } /* Given a binary tree, printInorder() prints out its inorder traversal*/ public virtual void printInorder(Node node) { if (node == null ) { return ; } /* first recur on left child */ printInorder(node.left); /* then print the data of node */ Console.Write(node.data + " " ); /* now recur on right child */ printInorder(node.right); } // Driver Code public static void Main( string [] args) { GFG tree = new GFG(); tree.root = new Node(50); tree.root.left = new Node(7); tree.root.right = new Node(2); tree.root.left.left = new Node(3); tree.root.left.right = new Node(5); tree.root.right.left = new Node(1); tree.root.right.right = new Node(30); Console.WriteLine( "Inorder traversal " + "before conversion is :" ); tree.printInorder(tree.root); tree.convertTree(tree.root); Console.WriteLine( "" ); Console.WriteLine( "Inorder traversal " + "after conversion is :" ); tree.printInorder(tree.root); } } // This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to convert an arbitrary binary tree // to a tree that holds children sum property class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } let root; /* This function changes a tree to hold children sum property */ function convertTree(node) { let left_data = 0, right_data = 0, diff; /* If tree is empty or it's a leaf node then return true */ if (node == null || (node.left == null && node.right == null )) return ; else { /* convert left and right subtrees */ convertTree(node.left); convertTree(node.right); /* If left child is not present then 0 is used as data of left child */ if (node.left != null ) left_data = node.left.data; /* If right child is not present then 0 is used as data of right child */ if (node.right != null ) right_data = node.right.data; /* get the diff of node's data and children sum */ diff = left_data + right_data - node.data; /* If node's children sum is greater than the node's data */ if (diff > 0) node.data = node.data + diff; /* THIS IS TRICKY --> If node's data is greater than children sum, then increment subtree by diff */ if (diff < 0) // -diff is used to make diff positive increment(node, -diff); } } /* This function is used to increment subtree by diff */ function increment(node, diff) { /* IF left child is not NULL then increment it */ if (node.left != null ) { node.left.data = node.left.data + diff; // Recursively call to fix the // descendants of node->left increment(node.left, diff); } else if (node.right != null ) // Else increment right child { node.right.data = node.right.data + diff; // Recursively call to fix the // descendants of node->right increment(node.right, diff); } } /* Given a binary tree, printInorder() prints out its inorder traversal*/ function printInorder(node) { if (node == null ) return ; /* first recur on left child */ printInorder(node.left); /* then print the data of node */ document.write(node.data + " " ); /* now recur on right child */ printInorder(node.right); } 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); document.write( "Inorder traversal before conversion is :" + "</br>" ); printInorder(root); convertTree(root); document.write( "</br>" ); document.write( "Inorder traversal after conversion is :" + "</br>" ); printInorder(root); </script> |
输出：
Inorder traversal before conversion is :3 7 5 50 1 2 30Inorder traversal after conversion is :14 19 5 50 1 31 30
时间复杂性： O（n^2），最坏情况下的复杂性是对于一棵扭曲的树，节点从根到叶的顺序是递减的。
如果您发现上述算法中存在任何缺陷，或者找到更好的方法来解决相同的问题，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
