Эки дарактын эки түйүнүнүн ортосундагы аралыкты табыңыз  


Кыйынчылык деңгээли жеңил
Көп суралган Amazon LinkedIn MakeMyTrip Netflix Samsung
Binary Tree дарак

Маселени билдирүү  

“Эки дарактын эки түйүнүнүн ортосундагы аралыкты табуу” маселеси сизге экилик дарак, ал эми сизге эки түйүн берилгенин билдирет. Эми ушул эки түйүндүн ортосундагы минималдуу аралыкты табышыңыз керек.

мисал  

Эки дарактын эки түйүнүнүн ортосундагы аралыкты табыңызтөөнөч

// 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

Эки дарактын Төмөнкү көрүнүшүн басып чыгаруу үчүн Java коду

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), бак-даракты бир нече жолу аралап өтүп жаткандыгына карабастан. Бирок бул полиномдук убакыттын татаалдыгын билдирбейт. Операциялардын бири - O (N) убакытта аткарылып жаткан эки түйүндүн LCAсын табуу. Андан кийин биз түйүндөрдүн тамырдан алыстыгын таап жатабыз, ал кайрадан O (1) убакытта жасалды. Бул убакыттын татаалдыгы боюнча "Эки дарактын эки түйүнүнүн ортосундагы аралыкты табуу" маселесин сызыктуу кылат.

ошондой эле
Бинардык издөө дарагын кыркыңыз

Космостун татаалдыгы

O (H), бул орун компилятор стеги үчүн талап кылынат. Анткени бардык функциялар рекурсивдүү функциялар, аларды колдоно алышат рекурсивдүү чөмөлө.