یک BST را به Tree با مقدار بیشتر تبدیل کنید


سطح دشواری متوسط
اغلب در آمازون بلومبرگ فیس بوک
درخت جستجوی دودویی درخت باینری درخت

برای تبدیل درخت BST به مقدار بیشتر با توجه به درخت جستجوی دودویی نوشتن یک الگوریتم برای تبدیل آن به یک درخت جمع بزرگتر ، یعنی تبدیل هر گره به شامل مجموع تمام عناصر بزرگتر از آن.

مثال

ورودی

یک BST را به Tree با مقدار بیشتر تبدیل کنید

تولید

یک BST را به Tree با مقدار بیشتر تبدیل کنید

پیش سفارش: 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

کد ++ 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;
}
69 81 87 34 54 0

رویکرد بهینه

روش فوق می تواند برای BST بهینه شود ، زیرا BST داده ها را به روشی کاملاً مشخص ذخیره می کند.
BST را به ترتیب معکوس ، یعنی راست-> ریشه-> شکل چپ عبور دهید. به این ترتیب ما گره ها را به ترتیب کمتری طی می کنیم و قبل از بازدید از هر گره ای ، گره های بزرگتر از آن را بازدید خواهیم کرد ، از این رو می توان مجموع همه گره های بزرگتر از یک گره را فقط در یک عبور از آن پیدا کرد.

  1. مقدار متغیر را به صورت 0 مقداردهی اولیه کنید ، با استفاده از مرجع منتقل می شود یا در سطح جهانی تعریف می شود.
  2. BST را به ترتیب معکوس رد کنید ، به این ترتیب داده ها را با ترتیب کمتری بدست خواهیم آورد.
  3. برای هر گره ای که ما عبور می کنیم ، مقدار آن را برابر با جمع می کنیم و مقدار آن را با مقدار اصلی گره افزایش می دهیم (قبل از به روزرسانی).

پیچیدگی زمان = O (N)
پیچیدگی فضا = 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

کد ++ 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;
}
69 81 87 34 54 0

منابع