이진 트리의 두 노드 사이의 거리 찾기


난이도 쉽게
자주 묻는 질문 아마존 링크드 인 MakeMyTrip 넷플릭스 삼성
이진 트리 나무

문제 정책

"바이너리 트리의 두 노드 사이의 거리 찾기"문제는 이진 트리가 제공되고 두 개의 노드가 제공됨을 나타냅니다. 이제이 두 노드 사이의 최소 거리를 찾아야합니다.

이진 트리의 두 노드 사이의 거리 찾기

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

이진 트리의 두 노드 사이의 거리를 찾는 방법

문제는 이진 트리의 두 노드 사이의 거리를 찾는 것을 요구합니다. 그래서 우리는 두 개의 노드와 이진 트리와 두 개의 노드가 주어질 것입니다. 이제이 두 노드 사이의 최소 거리를 찾아야합니다. 이것은 이진 트리의 고전적인 문제이며 일반적으로 n 항 트리에서 발생합니다. 우리는 사용하여 문제를 해결합니다 최소 공통 조상 나무의. 최소 공통 조상 또는 LCA는 두 노드에서 최소 거리에 있고 이러한 노드에서 트리 루트까지의 경로에있는 노드입니다. 하지만이 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) 시간에 수행되는 두 노드의 LCA를 찾는 것입니다. 그런 다음 O (1) 시간에 다시 수행되는 루트에서 노드의 거리를 찾습니다. 이것은 "바이너리 트리의 두 노드 사이의 거리 찾기"문제를 시간 복잡도 측면에서 선형 적으로 만듭니다.

공간 복잡성

오), 이 공간은 컴파일러 스택에 필요합니다. 모든 함수는 재귀 함수이기 때문에 재귀 스택.