BST Leetcode 솔루션의 최소 절대 차이


난이도 쉽게
자주 묻는 질문 구글
나무

BST Leetcode 솔루션의 최소 절대 차이 문제는 사용자에게 이진 검색 트리. 그리고 전체 BST에서 최소 절대 차이를 찾아야합니다. BST 또는 이진 검색 트리는 규칙을 따르는 일부 노드가있는 트리 일뿐입니다. 규칙은 노드의 왼쪽 하위 트리에 현재 노드보다 값이 작은 노드 만 포함되어야한다는 것입니다. 마찬가지로 오른쪽 하위 트리의 경우 노드에 현재 노드보다 큰 값이 포함되어야합니다. 따라서 평소와 같이 솔루션으로 이동하기 전에 먼저 몇 가지 예를 살펴보아야합니다.

BST Leetcode 솔루션의 최소 절대 차이

1

설명 : 노드 [1, 2], [2, 3], [3, 4], [4, 5]의 차이는 모두 1의 차이를 가지며 다른 모든 쌍은 더 큰 차이를 갖습니다. 따라서 답은 1입니다.

BST Leetcode 솔루션의 최소 절대 차이를위한 Brute Force 접근 방식

BST Leetcode 솔루션의 최소 절대 차이 문제는 주어진 이진 검색 트리에서 두 노드 간의 최소 차이를 찾도록 요청했습니다. 따라서 답을 찾는 한 가지 방법은 BST의 두 꼭지점 또는 노드를 선택하고 차이를 계산하는 것입니다. 이전 쌍보다 절대 차이가 적은 쌍을 찾으면 답변을 업데이트 할 것입니다. 처음에는 프로세스가 끝날 때 두 개의 노드를 사용할 수 있습니다. 답은 각 변수에 저장됩니다. 따라서이 프로세스를 시뮬레이션하기 위해 BST를 순서대로 탐색하고 벡터에 저장합니다. 두 개의 중첩 된 루프를 사용하여 트리의 모든 두 정점 간의 절대 차이를 계속 계산합니다.

무차별 대입 코드

BST Leetcode 솔루션의 최소 절대 차이를위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left, *right;
};

vector<int> inorder_traversal;
int ans = INT_MAX;

void inorder(TreeNode* root){
    if(root){
        inorder(root->left);
        inorder_traversal.push_back(root->val);
        inorder(root->right);
    }
}

int getMinimumDifference(TreeNode* root) {
    inorder(root);
    for(int i=1;i<inorder_traversal.size();i++)
        ans = min(ans, inorder_traversal[i]-inorder_traversal[i-1]);
    return ans;
}

int main(){
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->right = new TreeNode();
    root->right->val = 5;
    root->right->left = new TreeNode();
    root->right->left->val = 3;
    root->right->left->left = new TreeNode();
    root->right->left->left->val = 2;
    root->right->left->right = new TreeNode();
    root->right->left->right->val = 4;
    cout<<getMinimumDifference(root);
}
1

BST Leetcode 솔루션의 최소 절대 차이를위한 Java 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
}

class Main {
    static ArrayList<Integer> inorder_traversal = new ArrayList<Integer>();
    static int ans = Integer.MAX_VALUE;
    
    public static void inorder(TreeNode root){
        if(root != null){
            inorder(root.left);
            inorder_traversal.add(root.val);
            inorder(root.right);
        }
    }
    
    public static int getMinimumDifference(TreeNode root) {
        inorder(root);
        for(int i=1;i<inorder_traversal.size();i++)
        	ans = Math.min(ans, inorder_traversal.get(i)-inorder_traversal.get(i-1));
        return ans;
    }
    
    public static void main (String[] args) throws java.lang.Exception
  {
    TreeNode root = new TreeNode();
      root.val = 1;
      root.right = new TreeNode();
      root.right.val = 5;
      root.right.left = new TreeNode();
      root.right.left.val = 3;
      root.right.left.left = new TreeNode();
      root.right.left.left.val = 2;
      root.right.left.right = new TreeNode();
      root.right.left.right.val = 4;
      System.out.print(getMinimumDifference(root));
  }
}
1

복잡성 분석

시간 복잡성

O (N ^ 2), 최소 절대 차이를 찾기 위해 2 개의 중첩 루프를 사용했기 때문에이 접근 방식의 시간 복잡도는 다항식이됩니다.

공간 복잡성

의 위에), 벡터 나 배열에 inorder traversal을 저장해야했기 때문입니다. 따라서 공간 복잡성은 선형입니다.

BST Leetcode 솔루션의 최소 절대 차이를위한 최적화 된 접근 방식

BST Leetcode 솔루션의 최소 절대 차이 문제에 대한 위의 접근 방식은 inorder traversal을 사용했습니다. inorder traversal을 사용했을뿐만 아니라 그것을 저장하여 공간 복잡성 측면에서 O (N) 접근 방식을 만들었습니다. 또한 BST가 있다는 사실을 사용하지 않았으며 최소 절대 차이는 두 개의 연속 된 정점 사이에서만 얻을 수 있습니다. 사실을 고려하지 않았기 때문에 우리는 다항식 시간 복잡성을 가졌습니다.

최적화 된 접근 방식에서는 현재 정점에 대한 이전 노드를 추적합니다. 이렇게하면 평가 작업을 N-1 회만 수행하여 최소 절대 차이를 찾는 데 도움이됩니다. 이것은 또한 전체 inorder traversal을 저장할 필요가없고 이전 노드 만 저장할 필요가 있기 때문에 일정한 공간 복잡성을 달성하는 데 도움이됩니다.

BST Leetcode 솔루션의 최소 절대 차이를위한 최적화 된 코드

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left, *right;
};

TreeNode* previous = NULL;
int ans = INT_MAX;

void inorder(TreeNode* root){
    if(root){
        inorder(root->left);
        if(previous != NULL){
            ans = min(ans, root->val - previous->val);
        }
        previous = root;
        inorder(root->right);
    }
}

int getMinimumDifference(TreeNode* root) {
    inorder(root);
    return ans;
}

int main(){
    TreeNode* root = new TreeNode();
    root->val = 1;
    root->right = new TreeNode();
    root->right->val = 5;
    root->right->left = new TreeNode();
    root->right->left->val = 3;
    root->right->left->left = new TreeNode();
    root->right->left->left->val = 2;
    root->right->left->right = new TreeNode();
    root->right->left->right->val = 4;
    cout<<getMinimumDifference(root);
}
1

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
}

class Main {
    static TreeNode prev = null;
    static int ans = Integer.MAX_VALUE;
    
    public static void inorder(TreeNode root){
        if(root != null){
            inorder(root.left);
            if(prev != null){
                ans = Math.min(ans, root.val - prev.val);
            }
            prev = root;
            inorder(root.right);
        }
    }
    
    public static int getMinimumDifference(TreeNode root) {
        inorder(root);
        return ans;
    }
    
    public static void main (String[] args) throws java.lang.Exception
  {
    TreeNode root = new TreeNode();
      root.val = 1;
      root.right = new TreeNode();
      root.right.val = 5;
      root.right.left = new TreeNode();
      root.right.left.val = 3;
      root.right.left.left = new TreeNode();
      root.right.left.left.val = 2;
      root.right.left.right = new TreeNode();
      root.right.left.right.val = 4;
      System.out.print(getMinimumDifference(root));
  }
}
1

복잡성 분석

시간 복잡성

의 위에), 트리의 N 개 노드를 순회하는 inorder traversal 만 사용했기 때문입니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

O (1), 일정한 수의 변수 만 사용했기 때문입니다. 공간 복잡성도 일정한 공간으로 감소했습니다.