Перетворіть BST на дерево більшої суми


Рівень складності Medium
Часто запитують у Амазонка Bloomberg Facebook
Бінарне дерево пошуку Бінарне дерево Дерево

При перетворенні BST у велике дерево суми Дане бінарне дерево пошуку напишіть алгоритм щоб перетворити його у дерево більшої суми, тобто перетворити кожен вузол, щоб містити суму всіх елементів, більших за нього.

Приклад

вхід

Перетворіть BST на дерево більшої суми

Вихід

Перетворіть BST на дерево більшої суми

Попереднє замовлення: 69 81 87 34 54 0

Наївний підхід

Ідея дуже проста, траверс всі вузли по одному, і для кожного вузла знову обходити все дерево і знаходити суму вузлів, більшу за нього.
Зберігайте суму в масиві і після обчислення, суму для всіх вузлів, замініть вузли на відповідні суми. Цей підхід застосовний до будь-якого загального двійкового файлу дерево і не особливо для BST.

  1. Перемістіть заданий BST у порядку, вказаному в порядку.
  2. Для кожного вузла знову обведіть дерево у порядку, і знайдіть суму всіх вузлів, більших за поточний вузол.
  3. Зберігайте суму в масив або список.
  4. Після обходу всіх вузлів, знову обведіть дерево у формі в порядку і замініть кожен вузол відповідною сумою в масиві або списку.

Складність часу = О (н.)2)
Складність простору = O (h)
де n - кількість вузлів у дереві, а h - висота дерева.

Код JAVA для перетворення BST у дерево великих сум

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class TransformABSTToGreaterSumTree {
    // 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
        // replace its value with the corresponding sum
        if (root != null) {
            convertToGreaterSumTree(root.left, sumList);

            // change 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();
    }
}
69 81 87 34 54 0

Код С ++ для перетворення 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;
}
69 81 87 34 54 0

Оптимальний підхід

Вищезазначений підхід можна оптимізувати для BST, оскільки BST зберігає дані в дуже визначеному вигляді.
Пройдіть BST в зворотному порядку, тобто вправо-> корінь-> ліва форма. Таким чином ми будемо обходити вузли у порядку зменшення, і перед відвідуванням будь-якого вузла ми відвідаємо вузли, більші за нього, отже, ми можемо знайти суму всіх вузлів, більших за вузол, лише за один обхід.

  1. Ініціалізуйте суму змінної як 0, вона передається за посиланням або визначається глобально.
  2. Пройдіть BST в зворотному порядку в порядку, таким чином ми отримаємо дані в порядку зменшення.
  3. Для кожного вузла, який ми обходимо, робимо його значення рівним сумі і збільшуємо суму на початкове значення вузла (перед оновленням).

Складність часу = О (п)
Складність простору = O (h)
де n - загальна кількість вузлів у даному BST, а h - висота BST.

Код JAVA для перетворення BST у дерево великих сум

public class TransformABSTToGreaterSumTree {
    // 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 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();
    }
}
69 81 87 34 54 0

Код С ++ для перетворення 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;
}
69 81 87 34 54 0

посилання