모든 더 큰 키의 합계가 모든 키에 추가되도록 BST를 이진 트리로 변환

난이도 중급
자주 묻는 질문 Facebook
이진 검색 트리 이진 트리 나무조회수 49

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

이진 검색 트리가 주어지면 BST를 이진으로 변환하는 알고리즘 작성 나무 모든 더 큰 키의 합계가 모든 키에 추가되도록합니다.

입력

모든 더 큰 키의 합계가 모든 키에 추가되도록 BST를 이진 트리로 변환

산출

모든 더 큰 키의 합계가 모든 키에 추가되도록 BST를 이진 트리로 변환

선주문 : 81 87 88 54

순진한 접근

아이디어는 매우 간단합니다. 횡단 모든 노드를 하나씩, 각 노드에 대해 다시 전체 트리를 횡단하고 그보다 큰 노드의 합을 찾습니다. 합계를 배열에 저장하고 모든 노드의 합계를 계산 한 후 해당 합계로 노드를 증가시킵니다. 이 접근 방식은 모든 일반 이진 트리에 적용되며 BST에는 적용되지 않습니다.

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

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

BST를 이진 트리로 변환하기위한 JAVA 코드

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를 횡단합니다. 이런 식으로 우리는 내림차순으로 노드를 순회하고 어떤 노드를 방문하기 전에 그보다 큰 노드를 방문 할 것입니다. 따라서 한 번의 순회에서 노드보다 큰 모든 노드의 합계를 찾을 수 있습니다. 그것보다 큰 노드의 합으로.

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

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

BST를 이진 트리로 변환하기위한 JAVA 코드

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

균열 시스템 설계 인터뷰
Translate »