געפֿינען די ווייַטקייט צווישן צוויי נאָודז פון אַ ביינערי בוים


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן לינקעדין MakeMyTrip Netflix סאַמסונג
ביינערי טרי בוים

פּראָבלעם סטאַטעמענט

די פּראָבלעם "געפֿינען דיסטאַנסע צווישן צוויי נאָודז פון אַ ביינערי בוים" זאגט אַז איר האָט אַ ביינערי בוים און צוויי נאָודז. איצט איר דאַרפֿן צו געפֿינען די מינימום ווייַטקייט צווישן די צוויי נאָודז.

בייַשפּיל

געפֿינען די ווייַטקייט צווישן צוויי נאָודז פון אַ ביינערי בוים

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

צוגאַנג צו געפֿינען ווייַטקייט צווישן צוויי נאָודז פון אַ ביינערי בוים

דער פּראָבלעם פרעגט צו געפֿינען דיסטאַנסע צווישן צוויי נאָודז פון אַ ביינערי בוים. אַזוי מיר וועלן באַקומען צוויי נאָודז און אַ ביינערי בוים און צוויי נאָודז. איצט מיר דאַרפֿן צו געפֿינען די מינימום ווייַטקייט צווישן די צוויי נאָודז. דאָס איז אַ קלאסישע פּראָבלעם אויף ביינערי ביימער, און בכלל אין אַן N- ערי בוים. מיר סאָלווע די פּראָבלעם מיט די מינדסטער פּראָסט אַנסעסטאָר פון דעם בוים. דער קלענסטער פּראָסט אַנסעסטאָר אָדער לקאַ איז די נאָדע וואָס איז בייַ מינדסטער דיסטאַנסע פֿון ביידע די נאָודז און ליגן אויף די וועג פֿון די נאָודז צו דער וואָרצל פון דעם בוים. אָבער, ווי אַזוי די 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), אפילו כאָטש דער בוים איז דורכגעקאָכט קייפל מאָל. אָבער דאָס קען נישט קאַנסטאַטוט פּאַלינאָומיאַל צייט קאַמפּלעקסיטי. איינער פון די אַפּעריישאַנז איז צו געפֿינען די LCA פון צוויי נאָודז וואָס איז דורכגעקאָכט אין די O (N) צייט. דערנאָך מיר געפֿינען די ווייַטקייט פון נאָודז פֿון וואָרצל וואָס איז ווידער געטאן אין די O (1) צייט. דאָס מאכט די פּראָבלעם "געפֿינען ווייַטקייט צווישן צוויי נאָודז פון אַ ביינערי בוים" לינעאַר אין טערמינען פון צייט קאַמפּלעקסיטי.

ספעיס קאַמפּלעקסיטי

אוי), דעם פּלאַץ איז פארלאנגט פֿאַר די קאַמפּיילער אָנלייגן. ווייַל אַלע די פאַנגקשאַנז זענען רעקורסיווע פאַנגקשאַנז וואָס נוצן רעקורסיווע stack.