பைனரி மரத்தின் இரண்டு முனைகளுக்கு இடையிலான தூரத்தைக் கண்டறியவும்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் லின்க்டு இன் மேக்மைட்ரிப் நெட்ஃபிக்ஸ் சாம்சங்
பைனரி மரம் மரம்

சிக்கல் அறிக்கை  

“பைனரி மரத்தின் இரண்டு முனைகளுக்கிடையேயான தூரத்தைக் கண்டுபிடி” என்ற சிக்கல் உங்களுக்கு ஒரு பைனரி மரம் வழங்கப்படுவதாகவும் உங்களுக்கு இரண்டு முனைகள் வழங்கப்படுவதாகவும் கூறுகிறது. இப்போது நீங்கள் இந்த இரண்டு முனைகளுக்கும் இடையிலான குறைந்தபட்ச தூரத்தைக் கண்டுபிடிக்க வேண்டும்.

உதாரணமாக  

பைனரி மரத்தின் இரண்டு முனைகளுக்கு இடையிலான தூரத்தைக் கண்டறியவும்முள்

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

பைனரி மரத்தின் இரண்டு முனைகளுக்கு இடையிலான தூரத்தைக் கண்டறிய அணுகுமுறை  

ஒரு பைனரி மரத்தின் இரண்டு முனைகளுக்கு இடையில் தூரத்தைக் கண்டுபிடிக்க சிக்கல் கேட்கிறது. எனவே எங்களுக்கு இரண்டு முனைகளும் ஒரு பைனரி மரமும் இரண்டு முனைகளும் வழங்கப்படும். இப்போது இந்த இரண்டு முனைகளுக்கும் இடையிலான குறைந்தபட்ச தூரத்தை நாம் கண்டுபிடிக்க வேண்டும். இது பைனரி மரங்களில் ஒரு கிளாசிக்கல் பிரச்சினை, பொதுவாக ஒரு n-ary மரத்தில். ஐப் பயன்படுத்தி சிக்கலை தீர்க்கிறோம் குறைந்த பொதுவான மூதாதையர் மரத்தின். குறைந்த பொதுவான மூதாதையர் அல்லது எல்.சி.ஏ என்பது இரு முனைகளிலிருந்தும் குறைந்த தூரத்தில் இருக்கும் முனை மற்றும் இந்த முனைகளிலிருந்து மரத்தின் வேருக்கு செல்லும் பாதையில் உள்ளது. ஆனால் குறைந்தபட்ச தூரத்தை கணக்கிட இந்த எல்.சி.ஏ எவ்வாறு நமக்கு உதவுகிறது?

குறைந்தபட்ச தூரத்தின் பாதை எப்போதும் இரண்டு முனைகளின் எல்.சி.ஏ வழியாக செல்கிறது. எனவே, எப்படியாவது இரு முனைகளின் வேரிலிருந்தும் அவற்றின் எல்.சி.ஏவின் வேரிலிருந்தும் உள்ள தூரம் நமக்குத் தெரிந்தால். குறைந்தபட்ச தூரத்தைக் கண்டறிய எளிய சூத்திரத்தை நாம் கணக்கிடலாம். வேரிலிருந்து இரு முனைகளின் தூரத்தையும் சேர்ப்போம், பின்னர் மரத்தின் வேரிலிருந்து அவற்றின் எல்.சி.ஏவின் இரு மடங்கு தூரத்தைக் கழிப்போம். எனவே இல்

மேலும் காண்க
பைனரி மரத்தின் நிலை ஒழுங்கு

குறியீடு  

பைனரி மரத்தின் கீழ் காட்சியை அச்சிட சி ++ குறியீடு

#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 (1) நேரத்தில் மீண்டும் செய்யப்படும் மூலத்திலிருந்து முனைகளின் தூரத்தைக் கண்டுபிடிக்கிறோம். இது நேர சிக்கலின் அடிப்படையில் “பைனரி மரத்தின் இரண்டு முனைகளுக்கு இடையிலான தூரத்தைக் கண்டறியவும்” சிக்கலை உருவாக்குகிறது.

மேலும் காண்க
பைனரி தேடல் மரத்தை ஒழுங்கமைக்கவும்

விண்வெளி சிக்கலானது

ஓ (எச்), கம்பைலர் ஸ்டேக்கிற்கு இந்த இடம் தேவை. ஏனென்றால் அனைத்து செயல்பாடுகளும் சுழல்நிலை செயல்பாடுகளாக இருக்கின்றன, அவை பயன்படுத்துகின்றன சூத்திர ஸ்டாக்.