ระยะห่างขั้นต่ำระหว่าง BST Nodes Leetcode Solution


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Google
Recursion ต้นไม้

ปัญหาระยะทางขั้นต่ำระหว่าง BST Nodes Leetcode Solution ระบุว่าคุณได้รับ Binary Search Tree และคุณจะต้องค้นหาความแตกต่างขั้นต่ำทั้งหมด BST. ดังนั้นคุณต้องหาความแตกต่างสัมบูรณ์ขั้นต่ำระหว่างสองโหนดใน BST BST หรือ Binary Search Tree ไม่ใช่อะไรนอกจากต้นไม้ที่มีโหนดบางโหนดที่เป็นไปตามกฎ กฎคือทรีย่อยด้านซ้ายของโหนดต้องมีเฉพาะโหนดที่มีค่าน้อยกว่าโหนดปัจจุบัน ในทำนองเดียวกันสำหรับแผนผังย่อยที่ถูกต้องโหนดต้องมีค่าที่มากกว่าโหนดปัจจุบัน ดังนั้นตามปกติก่อนอื่นเราต้องดูตัวอย่างบางส่วนก่อนที่จะกระโดดลงไปในการแก้ปัญหา

ระยะห่างขั้นต่ำระหว่าง BST Nodes Leetcode Solution

1

คำอธิบาย: ความแตกต่างระหว่างโหนด [1, 2], [2, 3], [3, 4], [4, 5] ทั้งหมดมีความแตกต่างเป็น 1 และคู่อื่น ๆ ทั้งหมดมีความแตกต่างมากกว่า ดังนั้นคำตอบคือ 1

แนวทาง Brute Force สำหรับระยะห่างขั้นต่ำระหว่าง 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 ลูปที่ซ้อนกันเพื่อค้นหาความแตกต่างสัมบูรณ์ขั้นต่ำความซับซ้อนของเวลาสำหรับวิธีนี้จึงกลายเป็นพหุนาม

ความซับซ้อนของอวกาศ

บน)เนื่องจากเราต้องจัดเก็บการส่งผ่านตามลำดับในเวกเตอร์หรืออาร์เรย์ ดังนั้นความซับซ้อนของพื้นที่จึงเป็นเชิงเส้น

แนวทางที่ปรับให้เหมาะสมสำหรับระยะห่างขั้นต่ำระหว่าง BST Nodes Leetcode Solution

แนวทางข้างต้นสำหรับปัญหาการส่งผ่านตามลำดับ ไม่เพียง แต่ใช้ในการข้ามผ่านแบบ inorder เท่านั้น แต่ยังเก็บไว้ด้วยทำให้แนวทาง O (N) ในแง่ของความซับซ้อนของอวกาศ นอกจากนี้เรายังไม่ได้ใช้ข้อเท็จจริงที่ว่าเรามี BST และผลต่างสัมบูรณ์ขั้นต่ำสามารถหาได้ระหว่างจุดยอดสองจุดที่ต่อเนื่องกันเท่านั้น เนื่องจากไม่ได้คำนึงถึงความเป็นจริงเราจึงมีความซับซ้อนของเวลาพหุนาม

ในแนวทางที่ดีที่สุดเราจะติดตามโหนดก่อนหน้าไปยังจุดยอดปัจจุบัน การทำเช่นนี้ช่วยให้เราพบความแตกต่างสัมบูรณ์ขั้นต่ำโดยดำเนินการประเมินผลเพียง 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

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)เนื่องจากเราใช้ตัวแปรจำนวนคงที่เท่านั้น ความซับซ้อนของอวกาศยังลดลงเป็นพื้นที่คงที่