BST를 더 큰 합계 트리로 변환


난이도 중급
자주 묻는 질문 아마존 블룸버그 페이스북 서비스
이진 검색 트리 이진 트리 나무

BST를 더 큰 합계 트리로 변환 할 때 이진 검색 트리가 주어지면 연산 이를 더 큰 합계 트리로 변환합니다. 즉, 각 노드가 그보다 큰 모든 요소의 합계를 포함하도록 변환합니다.

입력

BST를 더 큰 합계 트리로 변환

산출

BST를 더 큰 합계 트리로 변환

선주문 : 69 81 87 34

순진한 접근

아이디어는 매우 간단합니다. 횡단 모든 노드를 하나씩, 각 노드에 대해 다시 전체 트리를 횡단하고 그보다 큰 노드의 합을 찾습니다.
합계를 배열에 저장하고 모든 노드의 합계를 계산 한 후 노드를 해당 합계로 바꿉니다. 이 접근 방식은 모든 일반 바이너리에 적용 할 수 있습니다. 나무 특히 BST는 아닙니다.

  1. 주어진 BST를 순서대로 순회합니다.
  2. 각 노드에 대해 다시 순서대로 트리를 탐색하고 현재 노드보다 큰 모든 노드의 합계를 찾습니다.
  3. 합계를 정렬 또는 명부.
  4. 모든 노드를 순회 한 후 다시 순서대로 트리를 순회하고 모든 노드를 배열 또는 목록의 해당 합계로 바꿉니다.

시간 복잡성 = 의 위에2)
공간 복잡성 = 오)
여기서 n은 트리의 노드 수이고 h는 트리의 높이입니다.

BST를 더 큰 합계 트리로 변환하기위한 JAVA 코드

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를 대 합계 트리로 변환하기위한 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;
}
69 81 87 34 54 0

최적의 접근 방식

BST는 매우 지정된 방식으로 데이터를 저장하므로 위의 접근 방식은 BST에 대해 최적화 할 수 있습니다.
역순으로 즉, 오른쪽-> 루트-> 왼쪽 형식으로 BST를 횡단합니다. 이런 식으로 우리는 내림차순으로 노드를 순회하고 어떤 노드를 방문하기 전에 그보다 큰 노드를 방문 할 것이므로 한 번의 순회에서 노드보다 큰 모든 노드의 합계를 찾을 수 있습니다.

  1. 변수 합계를 0으로 초기화하면 참조로 전달되거나 전역 적으로 정의됩니다.
  2. 역순 형식으로 BST를 통과하면 내림차순으로 데이터를 얻을 수 있습니다.
  3. 순회하는 각 노드에 대해 해당 값을 합계와 같게 만들고 노드의 원래 값만큼 합계를 증가시킵니다 (업데이트 전).

시간 복잡성 = O (N)
공간 복잡성 = 오)
여기서 n은 주어진 BST의 총 노드 수이고 h는 BST의 높이입니다.

BST를 더 큰 합계 트리로 변환하기위한 JAVA 코드

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를 대 합계 트리로 변환하기위한 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;
}
69 81 87 34 54 0

참조