حداقل فاصله بین گره های BST محلول Leetcode


سطح دشواری ساده
اغلب در گوگل
باز گشت درخت

مسئله حداقل فاصله بین گره های BST با راه حل Leetcode بیان می شود که یک درخت جستجوی باینری برای شما فراهم شده است. و شما ملزم به پیدا کردن حداقل اختلاف در کل هستید BST. بنابراین ، شما باید حداقل اختلاف مطلق بین هر دو گره را در BST پیدا کنید. BST یا درخت جستجوی دودویی چیزی نیست جز درختی با برخی گره ها که از یک قانون پیروی می کنند. قانون این است که زیر درخت چپ گره باید فقط شامل گره هایی باشد که مقداری کمتر از گره فعلی دارند. به همین ترتیب ، برای زیر درخت راست ، گره ها باید مقادیر بیشتری از گره فعلی داشته باشند. بنابراین ، طبق معمول ، ابتدا باید قبل از شروع به حل ، به چند نمونه نگاهی بیندازیم.

حداقل فاصله بین گره های BST محلول Leetcode

1

توضیح: اختلاف بین گره های [1 ، 2] ، [2 ، 3] ، [3 ، 4] ، [4 ، 5] همه اختلاف 1 دارند. و همه جفت های دیگر تفاوت بیشتری دارند. بنابراین پاسخ 1 است.

رویکرد Brute Force برای حداقل فاصله بین گره های BST محلول Leetcode

مسئله حداقل فاصله بین گره های BST ، راه حل Leetcode از ما خواسته است که حداقل اختلاف بین هر دو گره را در یک درخت جستجوی دودویی مشخص پیدا کنیم. بنابراین ، یکی از راه های یافتن پاسخ این است که هر دو راس یا گره BST را انتخاب کرده و تفاوت را محاسبه کنید. وقتی جفتی پیدا کنیم که اختلاف مطلق کمتری نسبت به جفت قبلی دارد ، پاسخ را به روز خواهیم کرد. در ابتدا می توانیم از هر دو گره و در پایان فرآیند استفاده کنیم. پاسخ در متغیرهای مربوطه ذخیره می شود. بنابراین ، برای شبیه سازی این فرآیند ، BST را به صورت بی نظیر رد می کنیم و آن را در یک بردار ذخیره می کنیم. با استفاده از دو حلقه تو در تو ، ما محاسبه اختلاف مطلق بین هر دو رئوس درخت را ادامه خواهیم داد.

Brute Force Code

کد C ++ برای حداقل فاصله بین گره های BST محلول Leetcode

#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 minDiffInBST(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<<minDiffInBST(root);
}
1

کد جاوا برای حداقل فاصله بین گره های BST راه حل کد

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 minDiffInBST(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(minDiffInBST(root));
  }
}
1

تحلیل پیچیدگی

پیچیدگی زمان

O (N ^ 2)، از آنجا که ما برای یافتن حداقل اختلاف مطلق از 2 حلقه تو در تو استفاده کرده ایم ، پیچیدگی زمانی برای این روش چند جمله ای می شود.

پیچیدگی فضا

بر)، زیرا ما مجبور بودیم مسیریابی inorder را در یک بردار یا آرایه ذخیره کنیم. بنابراین ، پیچیدگی فضا خطی است.

رویکرد بهینه شده برای حداقل فاصله بین گره های BST محلول Leetcode

رویکرد فوق برای عبور از معضل مشکل. نه تنها از پیمایش بی نظیر استفاده می کند ، بلکه همچنین آن را ذخیره می کند و از نظر پیچیدگی فضا ، رویکرد O (N) را ایجاد می کند. ما همچنین از این واقعیت که BST داشتیم استفاده نکردیم و حداقل اختلاف مطلق را فقط می توان بین دو راس متوالی بدست آورد. به دلیل اینکه در نظر گرفته نشده است ، ما دارای یک پیچیدگی زمانی چند جمله ای هستیم.

در رویکرد بهینه شده ، گره قبلی راس راس فعلی را ردیابی می کنیم. انجام این کار به ما کمک می کند تا با انجام عملیات ارزیابی فقط N-1 بار حداقل اختلاف مطلق را پیدا کنیم. این همچنین به ما کمک می کند تا به پیچیدگی فضایی ثابت دست پیدا کنیم زیرا مجبور نیستیم کل پیمایش بی نظیر را ذخیره کنیم و فقط گره قبلی را ذخیره کنیم.

کد بهینه شده برای حداقل فاصله بین گره های 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 minDiffInBST(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<<minDiffInBST(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 minDiffInBST(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(minDiffInBST(root));
  }
}
1

تحلیل پیچیدگی

پیچیدگی زمان

بر)، از آنجا که ما فقط از پیمایش غیرطبیعی استفاده کردیم که از گره های N روی درخت عبور می کند. بنابراین پیچیدگی زمان خطی است.

پیچیدگی فضا

O (1)، از آنجا که ما فقط تعداد ثابت متغیرها را استفاده می کنیم. پیچیدگی فضا نیز به فضای ثابت کاهش می یابد.