በሁለትዮሽ ዛፍ ሁለት አንጓዎች መካከል ያለውን ርቀት ያግኙ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን LinkedIn MakeMyTrip Netflix ሳምሰንግ
ሁለትዮሽ ዛፍ ዛፍ

የችግሩ መግለጫ  

ችግሩ “በሁለትዮሽ ዛፍ ሁለት አንጓዎች መካከል ያለውን ርቀት ፈልግ” የሚለው ሁለትዮሽ ዛፍ እንደተሰጠህ እና ሁለት አንጓዎች እንደተሰጠህ ይገልጻል ፡፡ አሁን በእነዚህ ሁለት አንጓዎች መካከል ዝቅተኛውን ርቀት መፈለግ ያስፈልግዎታል ፡፡

ለምሳሌ  

በሁለትዮሽ ዛፍ ሁለት አንጓዎች መካከል ያለውን ርቀት ያግኙጭንቅላታም መያያዣ መርፌ

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

በሁለትዮሽ ዛፍ በሁለት አንጓዎች መካከል ያለውን ርቀት ለመፈለግ አቀራረብ  

ችግሩ በሁለትዮሽ ኖት መካከል በሁለት አንጓዎች መካከል ያለውን ርቀት ለመፈለግ ይጠይቃል ፡፡ ስለዚህ ሁለት አንጓዎች እና ሁለትዮሽ ዛፍ እና ሁለት አንጓዎች ይሰጠናል ፡፡ አሁን በእነዚህ ሁለት አንጓዎች መካከል ዝቅተኛውን ርቀት መፈለግ አለብን ፡፡ ይህ በሁለትዮሽ ዛፎች ላይ እና በአጠቃላይ በ n-ary ዛፍ ውስጥ ክላሲካል ችግር ነው ፡፡ ችግሩን በመጠቀም እንፈታዋለን ቢያንስ የጋራ ቅድመ አያት የዛፉ ፡፡ በጣም አናሳ የሆነው የጋራ ቅድመ አያት ወይም ኤል.ሲ.ኤ. ከሁለቱም አንጓዎች ቢያንስ ቢያንስ ርቀት ያለው እና ከእነዚህ አንጓዎች እስከ ዛፉ ሥር ባለው መንገድ ላይ የሚተኛ መስቀለኛ መንገድ ነው ፡፡ ግን ይህ LCA ዝቅተኛውን ርቀት ለማስላት እንዴት ይረዳናል?

የዝቅተኛ ርቀት መንገድ ሁል ጊዜ በሁለቱ አንጓዎች LCA ውስጥ ያልፋል ፡፡ ስለዚህ ፣ እንደምንም የሁለቱም አንጓዎች ርቀትን ከ LCA ሥራቸው እና ከሥሩ ርቀትን የምናውቅ ከሆነ ፡፡ ዝቅተኛውን ርቀት ለማግኘት ቀለል ያለ ቀመር ማስላት እንችላለን። የሁለቱን አንጓዎች ርቀት ከሥሩ እንጨምራለን ከዚያም የ 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 (1) ጊዜ ውስጥ የሚከናወነውን የአንጓዎች ርቀትን እናገኛለን ፡፡ ይህ በጊዜ ውስብስብነት ላይ ችግርን “በሁለትዮሽ ዛፍ በሁለት አንጓዎች መካከል ርቀትን ፈልግ” መስመራዊ ያደርገዋል።

ተመልከት
የሁለትዮሽ ፍለጋ ዛፍ ይከርክሙ

የቦታ ውስብስብነት

ኦ (ኤች) ፣ ይህ ቦታ ለአቀናባሪው ቁልል ያስፈልጋል ፡፡ ምክንያቱም ሁሉም ተግባራት ተደጋጋሚ ተግባራት ናቸው ተደጋጋሚ ቁልል.