http://www.geeksforgeeks.org/convert-an-arbitrary-binary-tree-to-a-tree-that-holds-children-sum-property/
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <queue>
5 #include <stack>
6 using namespace std;
7
8 struct node {
9 int data;
10 struct node *left, *right;
11 node() : data(0), left(NULL), right(NULL) { }
12 node(int d) : data(d), left(NULL), right(NULL) { }
13 };
14
15 void print(node *node) {
16 if (!node) return;
17 print(node->left);
18 cout << node->data << " ";
19 print(node->right);
20 }
21
22 void _convert(node* root, int diff) {
23 if (!root) return;
24 if (root->left) {
25 root->left->data += diff;
26 _convert(root->left, diff);
27 }
28 else if (root->right) {
29 root->right->data += diff;
30 _convert(root->right, diff);
31 }
32 }
33
34 void convert(node* root) {
35 if (!root || !root->left && !root->right) return;
36 convert(root->left);
37 convert(root->right);
38 int sum = 0;
39 sum += root->left? root->left->data : 0;
40 sum += root->right? root->right->data : 0;
41 if (sum >= root->data) root->data = sum;
42 else _convert(root, root->data - sum);
43 }
44
45
46 int main() {
47 struct node* root = new node(50);
48 root->left = new node(7);
49 root->right = new node(2);
50 root->left->left = new node(3);
51 root->left->right = new node(5);
52 root->right->left = new node(1);
53 root->right->right = new node(30);
54 print(root);
55 cout << endl;
56 convert(root);
57 print(root);
58 return 0;
59 }