# BST到具有所有較小鍵總和的樹

## 天真的方法

1. 以順序形式遍歷給定的BST。
2. 對於每個節點，再次以任何遍歷形式遍歷樹，並找到所有小於當前節點的節點之和。
3. 將總和存儲在數組或列表中。
4. 遍歷所有節點後，再次按順序遍歷樹（必須與步驟1相同），並以數組或列表中的相應總和遞增每個節點。

### JAVA代碼，用於使用所有較小鍵的總和創建樹

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

public class BSTToATreeWithSumOfAllSmallerKeys {
// 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

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();
}
}```
`19 7 1 54 34 88`

### 用於使用所有較小鍵的總和創建樹的C ++代碼

```#include <bits/stdc++.h>
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 pre-order 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
// increment its value by sum
if (root != NULL) {
convertToGreaterSumTree(root->left, sumList);

// increment 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;
}```
`19 7 1 54 34 88`

## 最佳方法

1. 將變量sum初始化為0，通過引用傳遞或全局定義。
2. 以有序的形式遍歷BST，這樣我們將以遞增的順序獲取數據。
3. 對於我們遍歷的每個節點，將其值增加總和，並以節點的原始值增加總和（更新之前）。

### JAVA代碼，用於使用所有較小鍵的總和創建樹

```public class BSTToATreeWithSumOfAllSmallerKeys {
// 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);
}
}

// 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.left);

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

convertToGreaterSumTree(root.right);
}
}

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();
}
}```
`19 7 1 54 34 88`

### 用於使用所有較小鍵的總和創建樹的C ++代碼

```#include <bits/stdc++.h>
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 pre-order traversal of a binary tree
void preOrder(Node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}

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

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

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

convertToGreaterSumTree(root->right);
}
}

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;
}```
`19 7 1 54 34 88`