차례
문제 정책
"바이너리 트리의 두 노드 사이의 거리 찾기"문제는 이진 트리가 제공되고 두 개의 노드가 제공됨을 나타냅니다. 이제이 두 노드 사이의 최소 거리를 찾아야합니다.
예
// 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) 시간에 다시 수행되는 루트에서 노드의 거리를 찾습니다. 이것은 "바이너리 트리의 두 노드 사이의 거리 찾기"문제를 시간 복잡도 측면에서 선형 적으로 만듭니다.
