BST ไปยังต้นไม้ที่มีผลรวมของคีย์ที่เล็กกว่าทั้งหมด



ถามบ่อยใน บลูมเบิร์ก ดริชติ - ซอฟท์ ไมโครซอฟท์ ServiceNow Twitter ซอปเปอร์
ต้นไม้ค้นหาแบบไบนารี ต้นไม้ไบนารี ต้นไม้ ทรีทราเวอร์ซัล

ในปัญหานี้เราได้ให้ Binary Search Tree เขียนไฟล์ ขั้นตอนวิธี เพื่อแปลงสิ่งที่ดีที่สุดเป็นไฟล์ ต้นไม้ ด้วยผลรวมของคีย์ที่เล็กกว่าทั้งหมด

ตัวอย่าง

อินพุต

BST ไปยังต้นไม้ที่มีผลรวมของคีย์ที่เล็กกว่าทั้งหมด

เอาท์พุต

BST ไปยังต้นไม้ที่มีผลรวมของคีย์ที่เล็กกว่าทั้งหมด

สั่งล่วงหน้า: 19 7 1 54 34 88

แนวทางที่ไร้เดียงสา

ทราเวิร์ โหนดทั้งหมดทีละโหนดในรูปแบบการข้ามผ่านใด ๆ และสำหรับแต่ละโหนดสำรวจต้นไม้ทั้งหมดอีกครั้งและค้นหาผลรวมของโหนดทั้งหมดที่มีขนาดเล็กกว่า เก็บผลรวมนี้สำหรับทุกโหนดในอาร์เรย์เพิ่มโหนดทั้งหมดด้วยผลรวมที่สอดคล้องกัน แนวทางนี้ใช้ได้กับต้นไม้ไบนารีทั่วไปและไม่เฉพาะอย่างยิ่งสำหรับ BST

  1. สำรวจ BST ที่กำหนดในรูปแบบตามลำดับ
  2. สำหรับแต่ละโหนดให้สำรวจต้นไม้ในรูปแบบการข้ามผ่านอีกครั้งและค้นหาผลรวมของโหนดทั้งหมดที่มีขนาดเล็กกว่าโหนดปัจจุบัน
  3. เก็บผลรวมในอาร์เรย์หรือรายการ
  4. หลังจากข้ามโหนดทั้งหมดแล้วให้สำรวจโครงสร้างตามลำดับอีกครั้ง (ต้องเหมือนกับขั้นตอนที่ 1) และเพิ่มทุกโหนดด้วยผลรวมที่สอดคล้องกันในอาร์เรย์หรือรายการ

ความซับซ้อนของเวลา = บน2)
ความซับซ้อนของพื้นที่ = O (ซ)
โดยที่ n คือจำนวนโหนดในทรี

รหัส JAVA สำหรับสร้าง Tree พร้อม Sum ของคีย์ขนาดเล็กทั้งหมด

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

public class BSTToATreeWithSumOfAllSmallerKeys {
    // 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();
    }
}
19 7 1 54 34 88

รหัส C ++ สำหรับสร้าง Tree พร้อม Sum ของคีย์ขนาดเล็กทั้งหมด

#include <bits/stdc++.h> 
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 pre-order 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
    // increment its value by sum
    if (root != NULL) {
        convertToGreaterSumTree(root->left, sumList);
        
        // increment 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;
}
19 7 1 54 34 88

แนวทางที่เหมาะสมที่สุด

สำรวจ BST ในรูปแบบตามลำดับนั่นคือซ้าย -> รูท -> รูปแบบขวา ด้วยวิธีนี้เราจะสำรวจโหนดตามลำดับที่เพิ่มขึ้นและก่อนที่จะไปที่โหนดใด ๆ เราจะไปที่โหนดที่มีขนาดเล็กกว่าดังนั้นเราจะพบผลรวมของโหนดทั้งหมดที่มีขนาดเล็กกว่าโหนดในการส่งผ่านเพียงครั้งเดียวและด้วยเหตุนี้ในระหว่างการเพิ่มการข้ามผ่านทุกโหนด โดยผลรวมของโหนดที่เล็กกว่ามัน

  1. เริ่มต้นผลรวมของตัวแปรเป็น 0 ซึ่งจะถูกส่งผ่านโดยการอ้างอิงหรือกำหนดไว้ทั่วโลก
  2. สำรวจ BST ในรูปแบบตามลำดับด้วยวิธีนี้เราจะได้รับข้อมูลตามลำดับที่เพิ่มขึ้น
  3. สำหรับแต่ละโหนดที่เราสำรวจเพิ่มค่าด้วยผลรวมและผลรวมที่เพิ่มขึ้นตามค่าดั้งเดิมของโหนด (ก่อนอัปเดต)

ความซับซ้อนของเวลา = O (n)
ความซับซ้อนของพื้นที่ = O (ซ)
โดยที่ n คือจำนวนโหนดทั้งหมดใน BST ที่กำหนด

รหัส JAVA สำหรับสร้าง Tree พร้อม Sum ของคีย์ขนาดเล็กทั้งหมด

public class BSTToATreeWithSumOfAllSmallerKeys {
    // 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);
        }
    }

    // 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.left);

            // update the sum and increment the node's value
            int prevValue = root.data;
            root.data += sum;
            sum += prevValue;

            convertToGreaterSumTree(root.right);
        }
    }

    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();
    }
}
19 7 1 54 34 88

รหัส C ++ สำหรับสร้าง Tree พร้อม Sum ของคีย์ขนาดเล็กทั้งหมด

#include <bits/stdc++.h> 
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 pre-order traversal of a binary tree 
void preOrder(Node *root) { 
    if (root != NULL) { 
        cout<<root->data<<" "; 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 

// sum defined globally and initialized as 0
int sum = 0;

void convertToGreaterSumTree(Node *root) {
    // traverse the tree in reverse in-order form
    if (root != NULL) {
        convertToGreaterSumTree(root->left);
        
        // update the sum and increment the node's value
        int prevValue = root->data;
        root->data += sum;
        sum += prevValue;
        
        convertToGreaterSumTree(root->right);
    }
}

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;
}
19 7 1 54 34 88

อ้างอิง