BST ን ወደ ሁለትዮሽ ዛፍ ይለውጡ እንደዚህ ያሉ ታላላቅ ቁልፎች ድምር በእያንዳንዱ ቁልፍ ላይ ይታከላል


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ፌስቡክ
የሁለትዮሽ ፍለጋ ዛፍ ሁለትዮሽ ዛፍ ዛፍ

የሁለትዮሽ ፍለጋ ዛፍ ከተሰጠ BST ን ወደ ባለ ሁለትዮሽ ለመለወጥ ስልተ ቀመር ይፃፉ ዛፍ የሁሉም ታላላቅ ቁልፎች ድምር በእያንዳንዱ ቁልፍ ላይ ይታከላል ፡፡

ለምሳሌ

ግቤት

BST ን ወደ ሁለትዮሽ ዛፍ ይለውጡ እንደዚህ ያሉ ታላላቅ ቁልፎች ድምር በእያንዳንዱ ቁልፍ ላይ ይታከላል

ዉጤት

BST ን ወደ ሁለትዮሽ ዛፍ ይለውጡ እንደዚህ ያሉ ታላላቅ ቁልፎች ድምር በእያንዳንዱ ቁልፍ ላይ ይታከላል

ቅድመ-ትዕዛዝ-81 87 88 54 69 34

የዋህ አቀራረብ

ሀሳቡ በጣም ቀላል ነው ፣ መተላለፊያ ሁሉም አንጓዎች አንድ በአንድ ፣ እና ለእያንዳንዱ መስቀለኛ መንገድ እንደገና መላውን ዛፍ አቋርጠው ከእሱ የበለጠ የአንጓዎች ድምርን ያገኛሉ ፡፡ ድምርን በአንድ ድርድር ውስጥ ያከማቹ እና ከሂሳብ ስሌት በኋላ ለሁሉም አንጓዎች ድምር ፣ አንጓዎቹን በሚዛመዱ ድምርዎቻቸው ይጨምሩ። ይህ አካሄድ ለማንኛውም አጠቃላይ የሁለትዮሽ ዛፍ የሚተገበር ሲሆን በተለይም ለ BST አይደለም ፡፡

  1. የተሰጠውን BST በቅደም ተከተል ቅፅ ይጓዙ ፡፡
  2. ለእያንዳንዱ መስቀለኛ መንገድ እንደገና ዛፉን በቅደም ተከተል መልክ በማለፍ ከአሁኑ መስቀለኛ ክፍል የሚበልጡትን የአንጓዎች ሁሉ ድምር ያግኙ ፡፡
  3. ድምርን በአንድ ድርድር ወይም ዝርዝር ውስጥ ያከማቹ።
  4. ሁሉንም አንጓዎች ከተሻገሩ በኋላ እንደገና ዛፉን በቅደም ተከተል በማለፍ እያንዳንዱን መስቀለኛ መንገድ በድርድሩ ወይም በዝርዝሩ ውስጥ ካለው ተመሳሳይ መጠን ጋር ይጨምሩ።

የጊዜ ውስብስብነት = ኦ (n2)
የቦታ ውስብስብነት = ኦ (ሸ)
በዛፉ ውስጥ የአንጓዎች ብዛት ቁጥር n ነው ፡፡

አንድ 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

አንድ 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 ን በቅደም ተከተል በቅደም ተከተል ማለትም በቀኝ-> root-> በግራ ቅጽ ያቋርጡ። በዚህ መንገድ አንጓዎችን በቅደም ተከተል እናቋርጣቸዋለን እናም ማንኛውንም መስቀለኛ መንገድ ከመጎብኘትዎ በፊት ከእሱ የሚበልጡ አንጓዎችን እንጎበኛለን ፣ ስለሆነም በአንዱ ማቋረጫ ከአንድ መስቀለኛ ክፍል የበለጠ የሁሉም አንጓዎች ድምርን እናገኛለን እናም በዚህ ወቅት በእያንዳንዱ መስቀለኛ መንገድ መጨመር ውስጥ ፡፡ ከእሱ በሚበልጡት የአንጓዎች ድምር።

  1. ተለዋዋጭ ድምርን እንደ 0 ያስጀምሩ ፣ በማጣቀሻ ይተላለፋል ወይም በዓለም አቀፍ ይገለጻል።
  2. BST ን በቅደም ተከተል በቅደም ተከተል በቅደም ተከተል ያቋርጡ ፣ በዚህ መንገድ ውሂቡን በቅደም ተከተል እናገኛለን።
  3. ለእያንዳንዱ መስቀለኛ መንገድ እንጓዛለን ፣ ዋጋውን በድምሩ እና በመደወያው የመጀመሪያ እሴት (ከማዘመን በፊት) እንጨምራለን ፡፡

የጊዜ ውስብስብነት = ሆይ (n)
የቦታ ውስብስብነት = ኦ (ሸ)
በተጠቀሰው BST ውስጥ የአንጓዎች ጠቅላላ ቁጥር የት ነው ፡፡

አንድ 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

አንድ 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

ማጣቀሻ1     ማጣቀሻ 2