이진 검색 트리가 주어지면 BST를 이진으로 변환하는 알고리즘 작성 나무 모든 더 큰 키의 합계가 모든 키에 추가되도록합니다.
차례
예
입력
산출
선주문 : 81 87 88 54
순진한 접근
아이디어는 매우 간단합니다. 횡단 모든 노드를 하나씩, 각 노드에 대해 다시 전체 트리를 횡단하고 그보다 큰 노드의 합을 찾습니다. 합계를 배열에 저장하고 모든 노드의 합계를 계산 한 후 해당 합계로 노드를 증가시킵니다. 이 접근 방식은 모든 일반 이진 트리에 적용되며 BST에는 적용되지 않습니다.
- 주어진 BST를 순서대로 순회합니다.
- 각 노드에 대해 다시 순서대로 트리를 탐색하고 현재 노드보다 큰 모든 노드의 합계를 찾습니다.
- 합계를 배열 또는 목록에 저장합니다.
- 모든 노드를 순회 한 후 다시 순서대로 트리를 순회하고 배열 또는 목록의 해당 합계로 모든 노드를 증가시킵니다.
시간 복잡성 = 의 위에2)
공간 복잡성 = 오)
여기서 n은 트리의 노드 수입니다.
BST를 이진 트리로 변환하기위한 JAVA 코드
import java.util.ArrayList;
import java.util.LinkedList;
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<>();
queue.add(root);
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (curr.data > value) {
sum += curr.data;
}
if (curr.left != null)
queue.add(curr.left);
if (curr.right != null)
queue.add(curr.right);
}
// 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);
sumList.add(sum);
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
최적의 접근 방식
BST는 매우 지정된 방식으로 데이터를 저장하므로 위의 접근 방식은 BST에 대해 최적화 할 수 있습니다.
역순, 즉 오른쪽-> 루트-> 왼쪽 형식으로 BST를 횡단합니다. 이런 식으로 우리는 내림차순으로 노드를 순회하고 어떤 노드를 방문하기 전에 그보다 큰 노드를 방문 할 것입니다. 따라서 한 번의 순회에서 노드보다 큰 모든 노드의 합계를 찾을 수 있습니다. 그것보다 큰 노드의 합으로.
- 변수 합계를 0으로 초기화하면 참조로 전달되거나 전역 적으로 정의됩니다.
- 역순 형식으로 BST를 통과하면 내림차순으로 데이터를 얻을 수 있습니다.
- 순회하는 각 노드에 대해 해당 값을 합계로 증가시키고 합계를 노드의 원래 값만큼 증가시킵니다 (업데이트 전).
시간 복잡성 = O (N)
공간 복잡성 = 오)
여기서 n은 주어진 BST의 총 노드 수입니다.
BST를 이진 트리로 변환하기위한 JAVA 코드
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
