Преобразувайте BST в двоично дърво, така че сумата от всички по-големи ключове да се добавя към всеки ключ


Ниво на трудност M
Често задавани в Facebook
Двоично дърво за търсене Двоично дърво Дърво

Дадено бинарно дърво за търсене, напишете алгоритъм за конвертиране на BST в двоичен файл Дърво такъв, че сумата от всички по-големи ключове се добавя към всеки ключ.

Пример

Вход

Преобразувайте BST в двоично дърво, така че сумата от всички по-големи ключове да се добавя към всеки ключ

Продукция

Преобразувайте BST в двоично дърво, така че сумата от всички по-големи ключове да се добавя към всеки ключ

Предварителна поръчка: 81 87 88 54 69 34

Наивен подход

Идеята е много проста, траверса всички възли един по един и за всеки възел отново прекоси цялото дърво и намери сумата от възли по-голяма от него. Съхранявайте сумата в масив и след изчислението, сумата за всички възли, увеличете възлите със съответните им суми. Този подход е приложим за всяко общо двоично дърво и не особено за BST.

  1. Прекосете дадения BST в подредена форма.
  2. За всеки възел отново пресечете дървото под формата на ред и намерете сумата от всички възли, които са по-големи от текущия възел.
  3. Съхранявайте сумата в масив или списък.
  4. След като обходите всички възли, отново преместете дървото под формата на ред и увеличете всеки възел със съответната му сума в масива или списъка.

Сложност във времето = На2)
Сложност на пространството = O (h)
където n е броят на възлите в дървото.

JAVA код за конвертиране на BST в двоично дърво

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

C ++ код за конвертиране на BST в двоично дърво

#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 в обратен ред, т.е.дясно-> корен-> лява форма. По този начин ще прекосим възлите в намаляващ ред и преди да посетим който и да е възел, ще посетим възлите, по-големи от него, следователно можем да намерим сумата от всички възли, по-големи от възел, само в едно обхождане и следователно по време на това обръщане нараства всеки възел чрез сумата на възлите, по-големи от него.

  1. Инициализирайте променлива сума като 0, тя се предава чрез препратка или се дефинира глобално.
  2. Прекосете BST в обратна подредена форма, по този начин ще получим данните в намаляващ ред.
  3. За всеки възел прекосяваме, увеличаваме стойността му чрез сума и увеличаваме сумата от първоначалната стойност на възела (преди актуализиране).

Сложност във времето = О (п)
Сложност на пространството = O (h)
където n е общият брой възли в дадения BST.

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

C ++ код за конвертиране на BST в двоично дърво

#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

Референтен номер1     справка2