იპოვნეთ ორობითი ხის ორ კვანძს შორის მანძილი


Რთული ტური Easy
ხშირად ეკითხებიან Amazon LinkedIn MakeMyTrip Netflix Samsung
ორობითი ხე ხე

პრობლემის განცხადება

პრობლემა "იპოვნეთ ორობითი ხის ორ კვანძს შორის მანძილი" აცხადებს, რომ გეძლევათ ორობითი ხე და გეძლევათ ორი კვანძი. ახლა თქვენ უნდა იპოვოთ მინიმალური მანძილი ამ ორ კვანძს შორის.

მაგალითი

იპოვნეთ ორობითი ხის ორ კვანძს შორის მანძილი

// Tree is shown using the image above
node 1 = 9
node 2 = 4
3

მიდგომა იპოვნეთ ორობითი ხის ორ კვანძს შორის მანძილი

პრობლემა ითხოვს ორობითი ხის ორ კვანძს შორის მანძილის პოვნას. ასე რომ, ჩვენ მოგვეცემა ორი კვანძი და ორობითი ხე და ორი კვანძი. ახლა ჩვენ უნდა ვიპოვნოთ მინიმალური მანძილი ამ ორ კვანძს შორის. ეს კლასიკური პრობლემაა ბინარულ ხეებზე და ზოგადად n-ary ხეში. ჩვენ პრობლემას ვაგვარებთ სულ მცირე საერთო წინაპარი ხის. ყველაზე ნაკლებად საერთო წინაპარი ან LCA არის კვანძი, რომელიც მინიმუმ დაშორებულია ორივე კვანძიდან და მდებარეობს ამ კვანძებიდან ხის ფესვამდე მისასვლელ გზაზე. როგორ გვეხმარება ეს LCA მინიმალური მანძილის გამოთვლაში?

მინიმალური მანძილის გზა ყოველთვის გადის ორი კვანძის LCA- ში. ასე რომ, თუ როგორმე ვიცით ორივე კვანძის მანძილი ფესვიდან და მათი LCA მანძილი ფესვიდან. ჩვენ შეგვიძლია გამოვთვალოთ მარტივი ფორმულა, რომ იპოვოთ მინიმალური მანძილი. ჩვენ დავამატებთ ორივე კვანძის მანძილს ფესვიდან, შემდეგ გამოვაკლოთ ხის L ფესვიდან მათი LCA– ს მანძილზე ორჯერ. ასე რომ

კოდი

C ++ კოდი დაბეჭდვა ორობითი ხის ქვედა ხედი

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

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

// calculates distance for the node from the root
int findDistUtil(node* root, int n, int lev){
    if(!root)
        return -1;
    if(root->data == n)
        return lev;
    else{
        int left = findDistUtil(root->left, n, lev+1);
        int right = findDistUtil(root->right, n, lev+1);
        return (left != -1) ? left : right;
    }
}

node* findLCA(node* root, int n1, int n2){
    if(!root)
        return NULL;
    if(root->data == n1 || root->data == n2){
        return root;
    } else {
        // check if leftSubTree has n1 or n2 or both
        node* leftSubTree = findLCA(root->left, n1, n2);
        // check if rightSubTree has n1 or n2 or both
        node* rightSubTree = findLCA(root->right, n1, n2);
        if(leftSubTree && rightSubTree)
            return root;
        // if we don't find one nodes in left and one node in right subtree
        // then the lca must be either in left subtree or right subtree
        return (leftSubTree != NULL) ? leftSubTree : rightSubTree;
    }
}

int computeMinDistance(node* root, int n1, int n2){
    node* lca = findLCA(root, n1, n2);
    int n1dist = findDistUtil(root, n1, 0);
    int n2dist = findDistUtil(root, n2, 0);
    int lcadist = findDistUtil(root, lca->data, 0);
    return n1dist + n2dist - 2*lcadist;
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  cout<<computeMinDistance(root, 9, 4);
}
3

ჯავა კოდი დაბეჭდავს ორობითი ხის ქვედა ხედს

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  // calculates distance for the node from the root
  static int findDistUtil(node root, int n, int lev){
      if(root == null)
          return -1;
      if(root.data == n)
          return lev;
      else{
          int left = findDistUtil(root.left, n, lev+1);
          int right = findDistUtil(root.right, n, lev+1);
          return (left != -1) ? left : right;
      }
  }

  static node findLCA(node root, int n1, int n2){
      if(root == null)
          return null;
      if(root.data == n1 || root.data == n2){
          return root;
      } else {
          // check if leftSubTree has n1 or n2 or both
          node leftSubTree = findLCA(root.left, n1, n2);
          // check if rightSubTree has n1 or n2 or both
          node rightSubTree = findLCA(root.right, n1, n2);
          if(leftSubTree != null && rightSubTree != null)
              return root;
          // if we don't find one nodes in left and one node in right subtree
          // then the lca must be either in left subtree or right subtree
          return (leftSubTree != null) ? leftSubTree : rightSubTree;
      }
  }

  static int computeMinDistance(node root, int n1, int n2){
      node lca = findLCA(root, n1, n2);
      int n1dist = findDistUtil(root, n1, 0);
      int n2dist = findDistUtil(root, n2, 0);
      int lcadist = findDistUtil(root, lca.data, 0);
      return n1dist + n2dist - 2*lcadist;
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    System.out.print(computeMinDistance(root, 9, 4));
  }
}
3

სირთულის ანალიზი

დროის სირთულე

O (N), მიუხედავად იმისა, რომ ხე მრავალჯერ განიხილება. მაგრამ ეს არ წარმოადგენს პოლინომის დროის სირთულეს. ერთ – ერთი ოპერაცია არის ორი კვანძის LCA– ს პოვნა, რომელიც O (N) დროში ხდება. შემდეგ ჩვენ ვპოულობთ კვანძების მანძილს ფესვიდან, რაც კვლავ ხდება O (1) დროში. ეს ხდის პრობლემას ”იპოვნეთ მანძილი ორობითი ხის ორ კვანძს შორის” დროის სირთულის თვალსაზრისით.

სივრცის სირთულე

O (H), ეს სივრცე საჭიროა შემდგენელი სტეკისთვის. რადგან ყველა ფუნქცია არის რეკურსიული ფუნქცია, რომელიც გამოიყენებს რეკურსიული დასტის.