ໄລຍະຫ່າງຕ່ ຳ ສຸດລະຫວ່າງ NST Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ
Recursion ຕົ້ນໄມ້

ບັນຫາໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution ລະບຸວ່າທ່ານໄດ້ຖືກສະ ໜອງ ໃຫ້ກັບຕົ້ນໄມ້ການຄົ້ນຫາຖານສອງ. ແລະທ່ານ ຈຳ ເປັນຕ້ອງຊອກຫາຄວາມແຕກຕ່າງຂັ້ນຕ່ ຳ ໃນທັງ ໝົດ BST. ດັ່ງນັ້ນ, ທ່ານ ຈຳ ເປັນຕ້ອງຊອກຫາຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຢ່າງ ໜ້ອຍ ສຸດລະຫວ່າງສອງຂໍ້ໃນ BST. ຕົ້ນໄມ້ BST ຫຼື Binary Search Tree ແມ່ນບໍ່ມີຫຍັງເລີຍນອກຈາກຕົ້ນໄມ້ທີ່ມີຂໍ້ມູນບາງຢ່າງທີ່ປະຕິບັດຕາມກົດລະບຽບ. ກົດລະບຽບແມ່ນວ່າລັດຖະບັນຍັດເບື້ອງຊ້າຍຂອງ node ຕ້ອງມີພຽງແຕ່ຂໍ້ທີ່ມີຄຸນຄ່າ ໜ້ອຍ ກວ່າ node ປັດຈຸບັນ. ເຊັ່ນດຽວກັນ, ສຳ ລັບບົດບັນຍັດທີ່ຖືກຕ້ອງ, ຂໍ້ຕ້ອງມີຂໍ້ມູນທີ່ມີຄ່າສູງກວ່າ node ປັດຈຸບັນ. ສະນັ້ນ, ຕາມປົກກະຕິ, ກ່ອນອື່ນ ໝົດ ພວກເຮົາຕ້ອງໄດ້ເບິ່ງຕົວຢ່າງສອງສາມຢ່າງກ່ອນທີ່ຈະກ້າວເຂົ້າສູ່ການແກ້ໄຂ.

ໄລຍະຫ່າງຕ່ ຳ ສຸດລະຫວ່າງ NST Leetcode Solution

1

ຄຳ ອະທິບາຍ: ຄວາມແຕກຕ່າງລະຫວ່າງຂໍ້ [1, 2], [2, 3], [3, 4], [4, 5] ທັງ ໝົດ ມີຄວາມແຕກຕ່າງຂອງ 1. ແລະຄູ່ອື່ນໆມີຄວາມແຕກຕ່າງກັນຫຼາຍ. ສະນັ້ນ ຄຳ ຕອບແມ່ນ 1.

ວິທີການໃຊ້ ກຳ ລັງແຮງງານ ສຳ ລັບໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution

ບັນຫາໄລຍະຫ່າງລະຫວ່າງຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution ໄດ້ຂໍໃຫ້ພວກເຮົາຊອກຫາຄວາມແຕກຕ່າງຕ່ ຳ ສຸດລະຫວ່າງສອງຂໍ້ໃນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ. ດັ່ງນັ້ນ, ວິທີ ໜຶ່ງ ໃນການຊອກຫາ ຄຳ ຕອບແມ່ນການເລືອກເອົາສອງແນວຕັ້ງຫລືໂຫນດຂອງ BST ແລະຄິດໄລ່ຄວາມແຕກຕ່າງ. ພວກເຮົາຈະປັບປຸງ ຄຳ ຕອບເມື່ອພວກເຮົາພົບຄູ່ທີ່ມີຄວາມແຕກຕ່າງທີ່ສົມບູນກວ່າຄູ່ທີ່ຜ່ານມາ. ໃນເບື້ອງຕົ້ນ, ພວກເຮົາສາມາດໃຊ້ສອງຂໍ້, ແລະໃນຕອນທ້າຍຂອງຂະບວນການ. ຄຳ ຕອບຈະຖືກເກັບໄວ້ໃນຕົວແປຕ່າງໆ. ສະນັ້ນ, ເພື່ອ ຈຳ ລອງຂະບວນການນີ້, ພວກເຮົາຈະຂ້າມ BST ໃນແບບບໍ່ມີຕົວຕົນແລະເກັບມ້ຽນມັນຢູ່ໃນພາບ. ການນໍາໃຊ້ສອງວົງທີ່ມີຮັງ, ພວກເຮົາຈະສືບຕໍ່ຄິດໄລ່ຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງລະຫວ່າງສອງແນວຕັ້ງໃນຕົ້ນໄມ້.

ລະຫັດ Brute Force

ລະຫັດ C ++ ສຳ ລັບໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution

#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

ລະຫັດ Java ສຳ ລັບໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution

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 ວົງແຫວນໃນຮັງເພື່ອຊອກຫາຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງທີ່ສຸດ, ຄວາມສັບສົນເວລາ ສຳ ລັບວິທີການນີ້ຈະກາຍເປັນແບບ polynomial.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາຕ້ອງໄດ້ເກັບຮັກສາເສັ້ນທາງທີ່ບໍ່ມີຕົວຕົນໃນ vector ຫຼືຂບວນການ. ດັ່ງນັ້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.

ວິທີການທີ່ດີທີ່ສຸດ ສຳ ລັບໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution

ວິທີການຂ້າງເທິງນີ້ ສຳ ລັບບັນຫາການປ່ຽນເສັ້ນທາງ. ບໍ່ພຽງແຕ່ມັນໃຊ້ການເຄື່ອນຍ້າຍແບບບໍ່ມີຕົວຕົນເທົ່ານັ້ນ, ແຕ່ມັນຍັງເກັບມັນໄວ້, ເຮັດໃຫ້ວິທີການ O (N) ມີຄວາມສັບສົນໃນອະວະກາດ. ພວກເຮົາຍັງບໍ່ໄດ້ໃຊ້ຄວາມຈິງທີ່ວ່າພວກເຮົາມີ BST, ແລະຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດສາມາດໄດ້ຮັບໃນລະຫວ່າງສອງແນວຕັ້ງຕິດຕໍ່ກັນ. ຍ້ອນວ່າຄວາມຈິງບໍ່ໄດ້ ຄຳ ນຶງເຖິງ, ພວກເຮົາມີຄວາມສັບສົນດ້ານເວລາຫຼາຍໂພດ.

ໃນວິທີການທີ່ດີທີ່ສຸດ, ພວກເຮົາຕິດຕາມ node ກ່ອນ ໜ້າ ນີ້ກັບ vertex ປັດຈຸບັນ. ການເຮັດສິ່ງນີ້ຊ່ວຍໃຫ້ພວກເຮົາຊອກຫາຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດໂດຍການ ດຳ ເນີນການປະເມີນຜົນພຽງແຕ່ N-1 ເທົ່ານັ້ນ. ນີ້ຍັງຊ່ວຍໃຫ້ພວກເຮົາບັນລຸຄວາມສັບສົນໃນພື້ນທີ່ຄົງທີ່ເພາະວ່າພວກເຮົາບໍ່ ຈຳ ເປັນຕ້ອງເກັບຮັກສາເສັ້ນທາງຜ່ານທາງອິນເຕີເນັດທັງ ໝົດ, ແລະເກັບພຽງແຕ່ຂໍ້ທີ່ຜ່ານມາເທົ່ານັ້ນ.

ລະຫັດທີ່ດີທີ່ສຸດ ສຳ ລັບໄລຍະຫ່າງຂັ້ນຕ່ ຳ ສຸດລະຫວ່າງ BST Nodes Leetcode Solution

ລະຫັດ 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

Java Code

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), ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ພຽງແຕ່ການເດີນທາງແບບບໍ່ມີຕົວຕົນເຊິ່ງເຄື່ອນທີ່ຜ່ານຂໍ້ N ຢູ່ເທິງຕົ້ນໄມ້. ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ພຽງແຕ່ ຈຳ ນວນຕົວແປທີ່ຄົງທີ່ເທົ່ານັ້ນ. ຄວາມສັບສົນໃນອະວະກາດຍັງຫຼຸດລົງເປັນພື້ນທີ່ຄົງທີ່.