# 将BST转换为二叉树，以便将所有更大键的总和添加到每个键中

## 天真的方法

1. 以顺序形式遍历给定的BST。
2. 对于每个节点，再次以有序形式遍历树，并找到大于当前节点的所有节点的总和。
3. 将总和存储在数组或列表中。
4. 遍历所有节点后，再次按顺序遍历树，并以数组或列表中的相应总和递增每个节点。

### JAVA代码，用于将BST转换为二叉树

```import java.util.ArrayList;
import java.util.Queue;

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
// class representing the node of a binary tree
static class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
}
}

// function to print the pre-order traversal of a binary tree
private static void preOrder(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}

private static int findSum(Node root, int value) {
// if root is null, sum is 0
if (root == null) {
return 0;
}

// initialize sum as 0
int sum = 0;

// traverse the tree and find the sum of all the values greater than value
Queue<Node> queue = new LinkedList<>();

while (!queue.isEmpty()) {
Node curr = queue.poll();
if (curr.data > value) {
sum += curr.data;
}

if (curr.left != null)
if (curr.right != null)
}

// return sum
return sum;
}

private static void formSumList(Node root, Node curr, ArrayList<Integer> sumList) {
// traverse the tree in in-order form and for each node
// calculate the sum of elements greater than it
if (curr != null) {
formSumList(root, curr.left, sumList);

// Check for all the nodes to find the sum
int sum = findSum(root, curr.data);

formSumList(root, curr.right, sumList);
}
}

private static void  convertToGreaterSumTree(Node root, ArrayList<Integer> sumList) {
// traverse the tree in in-order form and for each node
// increment its value by sum
if (root != null) {
convertToGreaterSumTree(root.left, sumList);

// increment this value
root.data += sumList.get(0);
sumList.remove(0);

convertToGreaterSumTree(root.right, sumList);
}
}

public static void main(String[] args) {
// Example Tree
Node root = new Node(12);
root.left = new Node(6);
root.right = new Node(20);
root.left.left = new Node(1);
root.right.left = new Node(15);
root.right.right =  new Node(34);

ArrayList<Integer> sumList = new ArrayList<>();
formSumList(root, root, sumList);

convertToGreaterSumTree(root, sumList);

preOrder(root);
System.out.println();
}
}```
`81 87 88 54 69 34`

### 用于将BST转换为二叉树的C ++代码

```#include <iostream>
#include<vector>
#include<queue>
using namespace std;

// class representing node of a binary tree
class Node {
public:
int data;
Node *left;
Node *right;

Node(int d) {
data = d;
left = right = NULL;
}
};

// function to print the preorder traversal of a binary tree
void preOrder(Node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}

int findSum(Node *root, int value) {
// if root is null, sum is 0
if (root == NULL) {
return 0;
}

// initialize sum as 0
int sum = 0;

// traverse the tree and find the sum of all the values greater than value
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node *curr = q.front();
q.pop();
if (curr->data > value) {
sum += curr->data;
}
if (curr->left != NULL) {
q.push(curr->left);
}
if (curr->right != NULL) {
q.push(curr->right);
}
}

// return sum
return sum;
}

void formSumList(Node *root, Node *curr, vector<int> &sumList) {
// traverse the tree in in-order form and for each node
// calculate the sum of elements greater than it
if (curr != NULL) {
formSumList(root, curr->left, sumList);

// Check for all the nodes to find the sum
int sum = findSum(root, curr->data);
sumList.push_back(sum);
formSumList(root, curr->right, sumList);
}
}

void convertToGreaterSumTree(Node *root, vector<int> &sumList) {
// traverse the tree in in-order form and for each node
// replace its value with the corresponding sum
if (root != NULL) {
convertToGreaterSumTree(root->left, sumList);
// change this value
root->data += sumList[0];
sumList.erase(sumList.begin());
convertToGreaterSumTree(root->right, sumList);
}
}

int main() {
// Example Tree
Node *root = new Node(12);
root->left = new Node(6);
root->right = new Node(20);
root->left->left = new Node(1);
root->right->left = new Node(15);
root->right->right = new Node(34);

vector<int> sumList;
formSumList(root, root, sumList);

convertToGreaterSumTree(root, sumList);
preOrder(root);
cout<<endl;

return 0;
}```
`81 87 88 54 69 34`

## 最佳方法

1. 将变量sum初始化为0，通过引用传递或全局定义。
2. 以相反的顺序遍历BST，这样我们将以降序获取数据。
3. 对于我们遍历的每个节点，将其值增加总和，并以节点的原始值增加总和（更新之前）。

### JAVA代码，用于将BST转换为二叉树

```public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
// class representing node of a binary tree
static class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
}
}

// function to print the pre-order traversal of a binary tree
private static void preOrder(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}

// sum defined globally and initialized as 0
private static int sum = 0;

private static void convertToGreaterSumTree(Node root) {
// traverse the tree in reverse in-order form
if (root != null) {
convertToGreaterSumTree(root.right);

// update the sum and increment the node's value
int prevValue = root.data;
root.data += sum;
sum += prevValue;

convertToGreaterSumTree(root.left);
}
}

public static void main(String[] args) {
// Example Tree
Node root = new Node(12);
root.left = new Node(6);
root.right = new Node(20);
root.left.left = new Node(1);
root.right.left = new Node(15);
root.right.right =  new Node(34);

convertToGreaterSumTree(root);

preOrder(root);
System.out.println();
}
}```
`81 87 88 54 69 34`

### 用于将BST转换为二叉树的C ++代码

```#include <iostream>
#include<vector>
#include<queue>
using namespace std;

// sum defined globally and initialized as 0
int sum = 0;

// class representing node of a binary tree
class Node {
public:
int data;
Node *left;
Node *right;

Node(int d) {
data = d;
left = right = NULL;
}
};

// function to print the preorder traversal of a binary tree
void preOrder(Node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}

void convertToGreaterSumTree(Node *root) {
// traverse the tree in reverse in-order form
if (root != NULL) {
convertToGreaterSumTree(root->right);

// update the sum and the node's value
int prevValue = root->data;
root->data += sum;
sum += prevValue;

convertToGreaterSumTree(root->left);
}
}

int main() {
// Example Tree
Node *root = new Node(12);
root->left = new Node(6);
root->right = new Node(20);
root->left->left = new Node(1);
root->right->left = new Node(15);
root->right->right =  new Node(34);

convertToGreaterSumTree(root);

preOrder(root);
cout<<endl;

return 0;
}```
`81 87 88 54 69 34`