Пронајдете растојание помеѓу два јазли на бинарно дрво


Ниво на тешкотија Лесно
Често прашувано во Амазон Скопје MakeMyTrip Netflix Samsung
Бинарно дрво Дрво

Изјава за проблем

Проблемот „Пронајдете растојание помеѓу два јазли на бинарно дрво“ вели дека ви се дава бинарно дрво и ви се дадени два јазли. Сега треба да го пронајдете минималното растојание помеѓу овие два јазли.

пример

Пронајдете растојание помеѓу два јазли на бинарно дрво

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

Пристап за наоѓање на растојание помеѓу два јазли на бинарно дрво

Проблемот бара да се најде растојание помеѓу два јазли на Бинарно дрво. Значи, ќе ни бидат дадени два јазли и бинарно дрво и два јазли. Сега треба да го најдеме минималното растојание помеѓу овие два јазли. Ова е класичен проблем кај бинарните дрвја, и генерално кај дрвото. го решаваме проблемот користејќи го Најмалку заеднички предци на дрвото. Најмалку заеднички предци или LCA е јазол кој е на најмало растојание од двата јазли и лежи на патеката од овие јазли до коренот на дрвото. Но, како ни помага овој LCA да го пресметаме минималното растојание?

Патеката на минималното растојание секогаш поминува низ LCA на двата јазли. Значи, ако некако го знаеме растојанието на двата јазли од коренот и растојанието на нивниот LCA од коренот. Можеме да пресметаме едноставна формула за да го најдеме минималното растојание. Addе го додадеме растојанието на двата јазли од коренот, а потоа ќе го одземеме двојно растојанието на нивниот 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

Анализа на сложеност

Временска комплексност

НА), иако дрвото се поминува повеќе пати. Но, тоа не претставува полиномна временска сложеност. Една од операциите е да се најде LCA на два јазли што се прави во O (N) време. Тогаш го наоѓаме растојанието на јазлите од коренот што повторно се прави за време О (1). Ова го прави проблемот „Најди растојание помеѓу два јазли на бинарно дрво“ линеарен во однос на сложеноста на времето.

Комплексноста на просторот

О (H), овој простор е потребен за магацинот на компајлерот. Бидејќи сите функции се рекурзивни функции што ќе ги искористат рекурзивен магацинот.