이진 트리에서 두 노드의 가장 낮은 공통 조상을 찾는 방법은 무엇입니까?
이진 트리가 반드시 이진 검색 트리 일 필요는 없습니다.
구조는-
struct node {
int data;
struct node *left;
struct node *right;
};
친구와 함께 해결할 수있는 최대 솔루션은 이런 종류의 것이 었습니다. 이 바이너리 트리를
고려하십시오 .
순차 통과 수율-8, 4, 9, 2, 5, 1, 6, 3, 7
그리고 주문 후 순회 수익률-8, 9, 4, 5, 2, 6, 7, 3, 1
예를 들어 노드 8과 5의 공통 조상을 찾으려면 순서 트리 탐색에서 8과 5 사이에있는 모든 노드의 목록을 작성합니다.이 경우 [4, 9 , 2]. 그런 다음이 목록에서 어떤 노드가 postorder traversal (마지막 순회)에서 마지막으로 나타나는지 확인합니다. 따라서 8과 5의 공통 조상은 2입니다.
이 알고리즘의 복잡성은 O (n) (순서 / 후순 순회의 경우 O (n)이며 나머지 단계는 배열의 단순한 반복에 불과하기 때문에 O (n) 임)라고 생각합니다. 그러나 이것이 잘못되었을 가능성이 높습니다. :-)
그러나 이것은 매우 조잡한 접근법이며, 어떤 경우에 고장이 있는지 확실하지 않습니다. 이 문제에 대한 다른 (아마도 더 최적의) 해결책이 있습니까?
Nick Johnson은 부모 포인터가 없으면 O (n) 시간 복잡도 알고리즘이 최선의 방법이라는 것이 맞습니다.) 해당 알고리즘의 간단한 재귀 버전은 Kinding의 게시물 에서 O (n) 시간에 실행되는 코드를 참조하십시오. .
그러나 노드에 부모 포인터가 있으면 개선 된 알고리즘이 가능합니다. 문제의 두 노드 모두 노드에서 시작하여 부모를 삽입하여 루트에서 노드까지의 경로를 포함하는 목록을 구성하십시오.
예에서 8의 경우 {4}, {2, 4}, {1, 2, 4} (단계 표시)가 표시됩니다.
문제가있는 다른 노드에 대해서도 동일한 작업을 수행하여 결과가 표시되지 않습니다 (단계는 표시되지 않음) : {1, 2}
이제 목록이 다른 첫 번째 요소 또는 목록 중 하나의 마지막 요소 중 먼저 오는 요소를 찾도록 만든 두 목록을 비교하십시오.
이 알고리즘은 h (h) 시간이 필요합니다. 여기서 h는 트리의 높이입니다. 최악의 경우 O (h)는 O (n)과 동일하지만 트리가 균형을 이루면 O (log (n))입니다. 또한 O (h) 공간이 필요합니다. CEGRD의 게시물에 표시된 코드와 함께 일정한 공간 만 사용하는 개선 된 버전이 가능합니다.
트리 구성 방법에 관계없이 트리간에 변경하지 않고 트리에서 여러 번 수행하는 작업 인 경우 O (n) [선형] 시간 준비가 필요하지만 사용할 수있는 다른 알고리즘이 있습니다. 쌍은 O (1) [일정한] 시간 만 걸립니다. 이러한 알고리즘에 대한 참조는 Wikipedia 에서 가장 낮은 공통 조상 문제 페이지를 참조하십시오 . (이 링크를 처음 게시 한 Jason에게 감사의 말씀)
에서 시작 root노드와 하나가 모든 노드 발견하면 아래쪽으로 이동 p또는 q직접적인 자식으로 다음의 LCA입니다. (편집-이것은 노드의 값 p이거나 또는 q노드 값이면 반환해야합니다. 그렇지 않으면 노드 중 하나 p이거나 q다른 노드의 직계 자식 인 경우 실패 합니다.)
그렇지 않으면 p오른쪽 (또는 왼쪽) 서브 트리와 q왼쪽 (또는 오른쪽) 서브 트리 에서 노드를 찾으면 LCA입니다.
고정 코드는 다음과 같습니다.
treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {
// no root no LCA.
if(!root) {
return NULL;
}
// if either p or q is the root then root is LCA.
if(root==p || root==q) {
return root;
} else {
// get LCA of p and q in left subtree.
treeNodePtr l=findLCA(root->left , p , q);
// get LCA of p and q in right subtree.
treeNodePtr r=findLCA(root->right , p, q);
// if one of p or q is in leftsubtree and other is in right
// then root it the LCA.
if(l && r) {
return root;
}
// else if l is not null, l is LCA.
else if(l) {
return l;
} else {
return r;
}
}
}
아래 코드는 둘 중 하나가 다른 사람의 직계 자식 일 때 실패합니다.
treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {
// no root no LCA.
if(!root) {
return NULL;
}
// if either p or q is direct child of root then root is LCA.
if(root->left==p || root->left==q ||
root->right ==p || root->right ==q) {
return root;
} else {
// get LCA of p and q in left subtree.
treeNodePtr l=findLCA(root->left , p , q);
// get LCA of p and q in right subtree.
treeNodePtr r=findLCA(root->right , p, q);
// if one of p or q is in leftsubtree and other is in right
// then root it the LCA.
if(l && r) {
return root;
}
// else if l is not null, l is LCA.
else if(l) {
return l;
} else {
return r;
}
}
}
다음은 JAVA의 작업 코드입니다.
public static Node LCA(Node root, Node a, Node b) {
if (root == null) {
return null;
}
// If the root is one of a or b, then it is the LCA
if (root == a || root == b) {
return root;
}
Node left = LCA(root.left, a, b);
Node right = LCA(root.right, a, b);
// If both nodes lie in left or right then their LCA is in left or right,
// Otherwise root is their LCA
if (left != null && right != null) {
return root;
}
return (left != null) ? left : right;
}
지금까지 주어진 대답은 재귀를 사용하거나 예를 들어 메모리의 경로를 저장합니다.
매우 깊은 나무가 있으면이 두 가지 접근 방식이 모두 실패 할 수 있습니다.
다음은이 질문에 대한 답변입니다. 두 노드의 깊이 (루트로부터의 거리)를 확인할 때 노드가 같으면 두 노드에서 공통 조상을 향해 위로 안전하게 이동할 수 있습니다. 깊이 중 하나가 더 크면 다른 노드에 머무르면서 더 깊은 노드에서 위로 이동해야합니다.
코드는 다음과 같습니다.
findLowestCommonAncestor(v,w):
depth_vv = depth(v);
depth_ww = depth(w);
vv = v;
ww = w;
while( depth_vv != depth_ww ) {
if ( depth_vv > depth_ww ) {
vv = parent(vv);
depth_vv--;
else {
ww = parent(ww);
depth_ww--;
}
}
while( vv != ww ) {
vv = parent(vv);
ww = parent(ww);
}
return vv;
이 알고리즘의 시간 복잡도는 O (n)입니다. 이 알고리즘의 공간 복잡도는 O (1)입니다.
깊이의 계산과 관련하여 먼저 정의를 기억할 수 있습니다. v가 루트이면 depth (v) = 0; 그렇지 않으면 depth (v) = depth (parent (v)) + 1입니다. 다음과 같이 깊이를 계산할 수 있습니다.
depth(v):
int d = 0;
vv = v;
while ( vv is not root ) {
vv = parent(vv);
d++;
}
return d;
이런 종류의 이진 트리가 어떻게 구성되어 있는지에 따라 다릅니다. 아마도 당신은 나무의 뿌리가 주어지면 원하는 잎 노드를 찾는 방법이있을 것입니다-선택한 가지가 분기 될 때까지 두 값 모두에 적용하십시오.
루트가 주어지면 원하는 리프를 찾을 수있는 방법이 없다면 정상적인 작동과 마지막 공통 노드를 찾는 유일한 솔루션은 트리의 무차별 검색입니다.
http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html 에서 찾을 수 있습니다.
tree_node_type *LowestCommonAncestor(
tree_node_type *root , tree_node_type *p , tree_node_type *q)
{
tree_node_type *l , *r , *temp;
if(root==NULL)
{
return NULL;
}
if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);
if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}
Tarjan의 오프라인 최소 공통 조상 알고리즘 만으로도 충분합니다 ( Wikipedia 참조 ). Wikipedia 에 대한 문제 (가장 낮은 공통 조상 문제)가 더 있습니다 .
두 노드의 공통 조상을 찾으려면 :-
- 이진 검색을 사용하여 트리에서 지정된 노드 Node1을 찾고이 프로세스에서 방문한 모든 노드를 A1이라는 배열에 저장하십시오. 시간-O (로그온), 공간-O (로그온)
- 이진 검색을 사용하여 트리에서 지정된 Node2를 찾고이 프로세스에서 방문한 모든 노드를 A2라는 배열에 저장하십시오. 시간-O (로그온), 공간-O (로그온)
- A1 목록 또는 A2 목록이 비어 있으면 노드가 존재하지 않으므로 공통 조상이 없습니다.
- A1 목록과 A2 목록이 비어 있지 않으면 일치하지 않는 노드를 찾을 때까지 목록을 살펴보십시오. 이러한 노드를 찾으면 그 이전의 노드가 공통 조상입니다.
이진 검색 트리에서 작동합니다.
Java로 그림과 작업 코드를 사용하여 시도했지만
http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html
아래의 재귀 알고리즘은 균형 이진 트리에 대해 O (log N)에서 실행됩니다. getLCA () 함수에 전달 된 노드 중 하나가 루트와 동일하면 루트는 LCA가되고 어떤 영향도 수행 할 필요가 없습니다.
테스트 사례. [1] 두 노드 n1 및 n2는 트리에 있으며 부모 노드의 양쪽에 상주합니다. [2] 노드 n1 또는 n2는 루트이고 LCA는 루트입니다. [3] n1 또는 n2 만 트리에 있고 LCA는 트리 루트의 왼쪽 하위 트리의 루트 노드이거나 LCA는 트리 루트의 오른쪽 하위 트리의 루트 노드입니다.
[4] n1 또는 n2가 트리에 없으며 LCA가 없습니다. [5] n1과 n2는 서로 일직선에 있으며, LCA는 n1 또는 n2 중 하나이며 트리의 루트에 가장 가깝습니다.
//find the search node below root
bool findNode(node* root, node* search)
{
//base case
if(root == NULL)
return false;
if(root->val == search->val)
return true;
//search for the node in the left and right subtrees, if found in either return true
return (findNode(root->left, search) || findNode(root->right, search));
}
//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
//base case
if(root == NULL)
return NULL;
//If 1 of the nodes is the root then the root is the LCA
//no need to recurse.
if(n1 == root || n2 == root)
return root;
//check on which side of the root n1 and n2 reside
bool n1OnLeft = findNode(root->left, n1);
bool n2OnLeft = findNode(root->left, n2);
//n1 & n2 are on different sides of the root, so root is the LCA
if(n1OnLeft != n2OnLeft)
return root;
//if both n1 & n2 are on the left of the root traverse left sub tree only
//to find the node where n1 & n2 diverge otherwise traverse right subtree
if(n1OnLeft)
return getLCA(root->left, n1, n2);
else
return getLCA(root->right, n1, n2);
}
Ancestor를 찾아야하는 root지정된 노드 (예 : p및 q)가 동일한 하위 트리에있는 한 전체 트리에서 내려 가면됩니다 (값이 루트보다 작거나 더 큼).
이것은 루트에서 Lest Common Ancestor까지 똑바로 걸어 나무의 나머지 부분을 보지 않으므로 얻을 수있는 속도만큼 빠릅니다. 몇 가지 방법이 있습니다.
반복, O (1) 공간
파이썬
def lowestCommonAncestor(self, root, p, q):
while (root.val - p.val) * (root.val - q.val) > 0:
root = (root.left, root.right)[p.val > root.val]
return root
자바
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while ((root.val - p.val) * (root.val - q.val) > 0)
root = p.val < root.val ? root.left : root.right;
return root;
}
오버플로가 발생하면 (root.val-(long) p.val) * (root.val-(long) q.val)
재귀
파이썬
def lowestCommonAncestor(self, root, p, q):
next = p.val < root.val > q.val and root.left or \
p.val > root.val < q.val and root.right
return self.lowestCommonAncestor(next, p, q) if next else root
자바
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return (root.val - p.val) * (root.val - q.val) < 1 ? root :
lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}
스칼라에서 코드는 다음과 같습니다.
abstract class Tree
case class Node(a:Int, left:Tree, right:Tree) extends Tree
case class Leaf(a:Int) extends Tree
def lca(tree:Tree, a:Int, b:Int):Tree = {
tree match {
case Node(ab,l,r) => {
if(ab==a || ab ==b) tree else {
val temp = lca(l,a,b);
val temp2 = lca(r,a,b);
if(temp!=null && temp2 !=null)
tree
else if (temp==null && temp2==null)
null
else if (temp==null) r else l
}
}
case Leaf(ab) => if(ab==a || ab ==b) tree else null
}
}
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees
}
이 나무를 고려 
우리가 postorder와 preorder traversal을하고 첫 번째 공통 전임자와 후계자를 찾으면, 공통 조상을 얻게됩니다.
주문 후 => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 사전 주문 => 7,3,1,0,2,6,4 , 5,12,9,8,11,10,13,15,14
- 예 : 1
8,11의 최소 공통 조상
postorder에서 우리는 8 & 11 이후 => 9,14,15,13,12,7을가집니다. preorder에서 우리는 => 7,3,1,0,2,6,4,5,12,9가 8 & 11 이전입니다
9는 포스트 오더에서 8 & 11 이후와 프리오더에서 8 & 11 이전에 나타나는 첫 번째 공통 번호이므로 9가 답입니다.
- 예 : 2
5,10의 최소 공통 조상
주문 후 7,3,1,0,2,6,4에서 11,9,14,15,13,12,7
7은 주문 후 5,10 이후 및 선주문 후 5,10 이전에 발생하는 첫 번째 숫자이므로 7이 답입니다.
노드 x의 하위가 2 * x 및 2 * x + 1 인 풀 이진 트리 인 경우 더 빠른 방법이 있습니다.
int get_bits(unsigned int x) {
int high = 31;
int low = 0,mid;
while(high>=low) {
mid = (high+low)/2;
if(1<<mid==x)
return mid+1;
if(1<<mid<x) {
low = mid+1;
}
else {
high = mid-1;
}
}
if(1<<mid>x)
return mid;
return mid+1;
}
unsigned int Common_Ancestor(unsigned int x,unsigned int y) {
int xbits = get_bits(x);
int ybits = get_bits(y);
int diff,kbits;
unsigned int k;
if(xbits>ybits) {
diff = xbits-ybits;
x = x >> diff;
}
else if(xbits<ybits) {
diff = ybits-xbits;
y = y >> diff;
}
k = x^y;
kbits = get_bits(k);
return y>>kbits;
}
작동 원리
- 이진 검색을 사용하는 x & y를 나타내는 데 필요한 비트를 얻는다. O (log (32))
- x & y의 이진 표기법의 공통 접두사는 공통 조상입니다.
- 더 큰 비트 수로 표시되는 비트는 k >> diff로 동일한 비트로 표시됩니다.
- k = x ^ y는 x & y의 공통 접두사를 지 웁니다.
- 나머지 접미사를 나타내는 비트를 찾습니다.
- 접미사 비트로 x 또는 y를 이동하여 공통 조상 인 공통 접두사를 얻습니다.
이것은 기본적으로 더 큰 숫자를 두 숫자가 같을 때까지 재귀 적으로 나눕니다. 그 숫자는 공통 조상입니다. 나누는 것은 올바른 교대조입니다. 따라서 가장 가까운 조상을 찾으려면 두 숫자의 공통 접두사를 찾아야합니다.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
return left == null ? right : right == null ? left : root;
}
다음은 C ++ 방식입니다. 알고리즘을 가능한 한 쉽게 이해하려고 노력했습니다.
// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
typedef char type;
// Data members which would behave as place holders
const BinaryNode_t* m_pLCA;
type m_Node1, m_Node2;
static const unsigned int TOTAL_NODES = 2;
// The core function which actually finds the LCA; It returns the number of nodes found
// At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
unsigned int Search (const BinaryNode_t* const pNode)
{
if(pNode == 0)
return 0;
unsigned int found = 0;
found += (pNode->getData() == m_Node1);
found += (pNode->getData() == m_Node2);
found += Search(pNode->getLeft()); // below condition can be after this as well
found += Search(pNode->getRight());
if(found == TOTAL_NODES && m_pLCA == 0)
m_pLCA = pNode; // found !
return found;
}
public:
// Interface method which will be called externally by the client
const BinaryNode_t* Search (const BinaryNode_t* const pHead,
const type node1,
const type node2)
{
// Initialize the data members of the class
m_Node1 = node1;
m_Node2 = node2;
m_pLCA = 0;
// Find the LCA, populate to `m_pLCANode` and return
(void) Search(pHead);
return m_pLCA;
}
};
사용 방법:
LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
...
가장 낮은 공통 조상을 찾는 가장 쉬운 방법은 다음 알고리즘을 사용하는 것입니다.
루트 노드 검사
value1 및 value2가 루트 노드의 값보다 엄격히 작은 경우
왼쪽 하위 트리 검사
그렇지 않으면 value1 및 value2가 루트 노드의 값보다 엄격하게 큰 경우
오른쪽 하위 트리 검사
그밖에
루트를 반환
public int LCA(TreeNode root, int value 1, int value 2) {
while (root != null) {
if (value1 < root.data && value2 < root.data)
return LCA(root.left, value1, value2);
else if (value2 > root.data && value2 2 root.data)
return LCA(root.right, value1, value2);
else
return root
}
return null;
}
나는 해결책을 찾았다
- 순서대로
- 선주문
- 주문 후
3 개의 순회에 따라 누가 LCA인지 결정할 수 있습니다. LCA에서 두 노드의 거리를 찾으십시오. 이 두 거리를 더하면 답이됩니다.
여기 내가 생각하는 것입니다.
- fist 노드의 경로를 찾아 arr1에 저장하십시오.
- 루트에서 arr1까지의 모든 값을 확인하면서 2 노드의 경로를 찾기 시작하십시오.
- 값이 다른 시간은 종료합니다. 이전 일치 값은 LCA입니다.
복잡성 : 1 단계 : O (n), 2 단계 = ~ O (n), 총 = ~ O (n).
다음은 참조를위한 c # (. net)의 두 가지 접근 방식입니다.
이진 트리에서 OCA를 찾는 재귀 버전 (O (N)-최대 각 노드가 방문 할 때) (솔루션의 주요 지점은 LCA 임) (a) 두 요소가 하위 트리의 한쪽에있는 이진 트리의 유일한 노드 (왼쪽) 그리고 오른쪽) LCA입니다. (b) 또한 어느 노드가 어느쪽에 있는지 중요하지 않습니다. 처음에 나는 그 정보를 유지하려고 노력했으며 분명히 재귀 함수가 너무 혼란 스럽습니다.
두 노드 (O (N))를 검색하고 경로를 추적합니다 (추가 공간 사용-따라서 1 진은 이진 트리가 균형이 잘 잡혀 있으면 공간이 무시할 수 있다고 생각하더라도 더 좋습니다. O (로그 (N)).
경로를 비교할 수 있도록 (허용 된 답변과 비슷하지만, 이진 트리 노드에 포인터 노드가 없다고 가정하여 경로가 계산 됨)
BST의 LCA 완료 ( 질문과 관련이 없음 ) (O (log (N))
테스트
재귀 :
private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode,
int e1, int e2)
{
Debug.Assert(e1 != e2);
if(treeNode == null)
{
return null;
}
if((treeNode.Element == e1)
|| (treeNode.Element == e2))
{
//we don't care which element is present (e1 or e2), we just need to check
//if one of them is there
return treeNode;
}
var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
if(nLeft != null && nRight != null)
{
//note that this condition will be true only at least common ancestor
return treeNode;
}
else if(nLeft != null)
{
return nLeft;
}
else if(nRight != null)
{
return nRight;
}
return null;
}
위의 개인 재귀 버전은 다음 공용 메소드에 의해 호출됩니다.
public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
{
var n = this.FindNode(this._root, e1);
if(null == n)
{
throw new Exception("Element not found: " + e1);
}
if (e1 == e2)
{
return n;
}
n = this.FindNode(this._root, e2);
if (null == n)
{
throw new Exception("Element not found: " + e2);
}
var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
if (null == node)
{
throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
}
return node;
}
두 노드의 경로를 추적하여 해결하십시오.
public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
{
var path1 = new List<BinaryTreeNode>();
var node1 = this.FindNodeAndPath(this._root, e1, path1);
if(node1 == null)
{
throw new Exception(string.Format("Element {0} is not found", e1));
}
if(e1 == e2)
{
return node1;
}
List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
var node2 = this.FindNodeAndPath(this._root, e2, path2);
if (node1 == null)
{
throw new Exception(string.Format("Element {0} is not found", e2));
}
BinaryTreeNode lca = null;
Debug.Assert(path1[0] == this._root);
Debug.Assert(path2[0] == this._root);
int i = 0;
while((i < path1.Count)
&& (i < path2.Count)
&& (path2[i] == path1[i]))
{
lca = path1[i];
i++;
}
Debug.Assert(null != lca);
return lca;
}
여기서 FindNodeAndPath는 다음과 같이 정의됩니다.
private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
{
if(node == null)
{
return null;
}
if(node.Element == e)
{
path.Add(node);
return node;
}
var n = this.FindNodeAndPath(node.Left, e, path);
if(n == null)
{
n = this.FindNodeAndPath(node.Right, e, path);
}
if(n != null)
{
path.Insert(0, node);
return n;
}
return null;
}
BST (LCA)-관련 없음 (참조 용으로 만 완료)
public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
{
//ensure both elements are there in the bst
var n1 = this.BstFind(e1, throwIfNotFound: true);
if(e1 == e2)
{
return n1;
}
this.BstFind(e2, throwIfNotFound: true);
BinaryTreeNode leastCommonAcncestor = this._root;
var iterativeNode = this._root;
while(iterativeNode != null)
{
if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
{
iterativeNode = iterativeNode.Left;
}
else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
{
iterativeNode = iterativeNode.Right;
}
else
{
//i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
return iterativeNode;
}
}
//control will never come here
return leastCommonAcncestor;
}
단위 테스트
[TestMethod]
public void LeastCommonAncestorTests()
{
int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
BinarySearchTree bst = new BinarySearchTree();
foreach (int e in a)
{
bst.Add(e);
bst.Delete(e);
bst.Add(e);
}
for(int i = 0; i < b.Length; i++)
{
var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
Assert.IsTrue(n.Element == b[i]);
var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
Assert.IsTrue(n1.Element == b[i]);
Assert.IsTrue(n == n1);
var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
Assert.IsTrue(n2.Element == b[i]);
Assert.IsTrue(n2 == n1);
Assert.IsTrue(n2 == n);
}
}
의사 코드에 관심이있는 사람 (대학 가정 작업용)이 여기에 있습니다.
GETLCA(BINARYTREE BT, NODE A, NODE B)
IF Root==NIL
return NIL
ENDIF
IF Root==A OR root==B
return Root
ENDIF
Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)
IF Left! = NIL AND Right! = NIL
return root
ELSEIF Left! = NIL
Return Left
ELSE
Return Right
ENDIF
이것은 이미 답변되었지만 C 프로그래밍 언어를 사용 하여이 문제에 대한 나의 접근 방식입니다. 코드는 이진 검색 트리를 보여 주지만 (insert ()에 관한 한) 알고리즘은 이진 트리에서도 작동합니다. 아이디어는 순차 순회에서 노드 A에서 노드 B로있는 모든 노드를 검토하고 사후 순회에서 이들의 인덱스를 조회하는 것입니다. 사후 순회에서 최대 색인이있는 노드가 가장 낮은 공통 조상입니다.
이진 트리에서 가장 낮은 공통 조상을 찾는 함수를 구현하는 작동하는 C 코드입니다. 모든 유틸리티 함수 등도 제공하고 있지만 빨리 이해하려면 CommonAncestor ()로 이동하십시오.
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>
static inline int min (int a, int b)
{
return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
return ((a > b) ? a : b);
}
typedef struct node_ {
int value;
struct node_ * left;
struct node_ * right;
} node;
#define MAX 12
int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};
createNode(int value)
{
node * temp_node = (node *)malloc(sizeof(node));
temp_node->left = temp_node->right = NULL;
temp_node->value = value;
return temp_node;
}
node *
insert(node * root, int value)
{
if (!root) {
return createNode(value);
}
if (root->value > value) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
}
return root;
}
/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
static int i = 0;
if (!root) return;
inorder(root->left, IN);
IN[i] = root->value;
i++;
inorder(root->right, IN);
}
/* Builds post traversal path in the POST array */
void
postorder (node * root, int * POST)
{
static int i = 0;
if (!root) return;
postorder(root->left, POST);
postorder(root->right, POST);
POST[i] = root->value;
i++;
}
int
findIndex(int * A, int value)
{
int i = 0;
for(i = 0; i< MAX; i++) {
if(A[i] == value) return i;
}
}
int
CommonAncestor(int val1, int val2)
{
int in_val1, in_val2;
int post_val1, post_val2;
int j=0, i = 0; int max_index = -1;
in_val1 = findIndex(IN_ORDER, val1);
in_val2 = findIndex(IN_ORDER, val2);
post_val1 = findIndex(POST_ORDER, val1);
post_val2 = findIndex(POST_ORDER, val2);
for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
for(j = 0; j < MAX; j++) {
if (IN_ORDER[i] == POST_ORDER[j]) {
if (j > max_index) {
max_index = j;
}
}
}
}
printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
return max_index;
}
int main()
{
node * root = NULL;
/* Build a tree with following values */
//40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
root = insert(root, 40);
insert(root, 20);
insert(root, 10);
insert(root, 30);
insert(root, 5);
insert(root, 15);
insert(root, 25);
insert(root, 35);
insert(root, 1);
insert(root, 80);
insert(root, 60);
insert(root, 100);
/* Get IN_ORDER traversal in the array */
inorder(root, IN_ORDER);
/* Get post order traversal in the array */
postorder(root, POST_ORDER);
CommonAncestor(1, 100);
}
한 가지 더 접근 할 수 있습니다. 그러나 이미 답변에서 제안한 것만 큼 효율적이지 않습니다.
노드 n1에 대한 경로 벡터를 만듭니다.
노드 n2에 대한 두 번째 경로 벡터를 만듭니다.
해당 노드의 세트 노드를 암시하는 경로 벡터는 해당 노드에 도달하기 위해 통과합니다.
두 경로 벡터를 비교하십시오. 일치하지 않는 인덱스는 해당 인덱스-1의 노드를 반환합니다. 그러면 LCA가 제공됩니다.
이 접근법의 단점 :
경로 벡터를 계산하려면 트리를 두 번 횡단해야합니다. 경로 벡터를 저장하려면 추가 O (h) 공간이 필요합니다.
그러나 이것은 구현하고 이해하기도 쉽습니다.
경로 벡터를 계산하는 코드 :
private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {
if (treeNode == null) {
return false;
}
pathVector [index++] = treeNode.getKey ();
if (treeNode.getKey () == key) {
return true;
}
if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) ||
findPathVector (treeNode.getRightChild(), key, pathVector, index)) {
return true;
}
pathVector [--index] = 0;
return false;
}
이렇게 해봐
node * lca(node * root, int v1,int v2)
{
if(!root) {
return NULL;
}
if(root->data == v1 || root->data == v2) {
return root;}
else
{
if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
{
return root;
}
if(v1 < root->data && v2 < root->data)
{
root = lca(root->left, v1, v2);
}
if(v1 > root->data && v2 > root->data)
{
root = lca(root->right, v1, v2);
}
}
return root;
}
조잡한 방법 :
- 모든 노드에서
- X = n1, n2 중 하나가 노드의 왼쪽에 있는지 확인
- Y = n1, n2 중 하나가 노드의 오른쪽에 있는지 확인
- 노드 자체가 n1 인 경우 || n2, 우리는 일반화를 위해 왼쪽 또는 오른쪽에있는 것으로 부를 수 있습니다.
- X와 Y가 모두 참이면 노드는 CA입니다.
위 방법의 문제점은 "찾기"를 여러 번 수행한다는 것입니다. 즉, 각 노드가 여러 번 순회 할 가능성이 있습니다. 정보를 다시 처리하지 않도록 기록 할 수 있으면이 문제를 극복 할 수 있습니다 (동적 프로그래밍 생각).
따라서 모든 노드 찾기를 수행하는 대신 이미 발견 된 사항에 대한 기록을 유지합니다.
더 좋은 방법:
- left_set (왼쪽 하위 트리에서 n1 | n2가 발견 된 경우) 또는 깊이 우선 방식으로 right_set 인 경우 주어진 노드에 대해 확인합니다. (참고 : n1 | n2 인 경우 root 자체에 left_set의 속성을 부여합니다)
- left_set 및 right_set 둘 다인 경우 노드는 LCA입니다.
암호:
struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
int left_set, right_set;
left_set = right_set = 0;
struct Node *leftCA, *rightCA;
leftCA = rightCA = NULL;
if (root == NULL) {
return NULL;
}
if (root == n1 || root == n2) {
left_set = 1;
if (n1 == n2) {
right_set = 1;
}
}
if(!left_set) {
leftCA = findCA(root->left, n1, n2, &left_set);
if (leftCA) {
return leftCA;
}
}
if (!right_set) {
rightCA= findCA(root->right, n1, n2, &right_set);
if(rightCA) {
return rightCA;
}
}
if (left_set && right_set) {
return root;
} else {
*set = (left_set || right_set);
return NULL;
}
}
너비 우선 검색을위한 코드 두 노드가 모두 트리에 있는지 확인하십시오. 그런 다음에 만 LCA 검색을 진행하십시오. 개선 할 제안이 있으면 의견을 말하십시오. 아마도 방문한 것으로 표시하고 두 번째 노드를 개선하기 위해 중단 한 특정 지점에서 검색을 다시 시작할 수 있다고 생각합니다 (표시되지 않은 경우).
public class searchTree {
static boolean v1=false,v2=false;
public static boolean bfs(Treenode root, int value){
if(root==null){
return false;
}
Queue<Treenode> q1 = new LinkedList<Treenode>();
q1.add(root);
while(!q1.isEmpty())
{
Treenode temp = q1.peek();
if(temp!=null) {
q1.remove();
if (temp.value == value) return true;
if (temp.left != null) q1.add(temp.left);
if (temp.right != null) q1.add(temp.right);
}
}
return false;
}
public static Treenode lcaHelper(Treenode head, int x,int y){
if(head==null){
return null;
}
if(head.value == x || head.value ==y){
if (head.value == y){
v2 = true;
return head;
}
else {
v1 = true;
return head;
}
}
Treenode left = lcaHelper(head.left, x, y);
Treenode right = lcaHelper(head.right,x,y);
if(left!=null && right!=null){
return head;
}
return (left!=null) ? left:right;
}
public static int lca(Treenode head, int h1, int h2) {
v1 = bfs(head,h1);
v2 = bfs(head,h2);
if(v1 && v2){
Treenode lca = lcaHelper(head,h1,h2);
return lca.value;
}
return -1;
}
}
상위 노드가 없으면 순회가있는 솔루션이 O (n) 시간 복잡성을 줄 것입니다.
순회 방식 노드 A와 B에 대해 LCA를 찾고 있다고 가정하면 가장 간단한 방법은 먼저 루트에서 A 로의 경로를 얻은 다음 루트에서 B 로의 경로를 얻는 것입니다.이 두 경로가 있으면 쉽게 반복 할 수 있습니다. A와 B의 가장 낮은 공통 조상 인 마지막 공통 노드를 찾으십시오.
재귀 솔루션 또 다른 방법은 재귀를 사용하는 것입니다. 먼저 왼쪽 트리와 오른쪽 트리에서 LCA를 얻을 수 있습니다 (있는 경우). A 또는 B 중 하나가 루트 노드 인 경우 루트는 LCA이며 루트 만 반환합니다.이 루트는 재귀의 끝점입니다. 트리를 하위 트리로 계속 나누면 결국 A와 B를칩니다.
하위 문제 해결 방법을 결합하기 위해 LCA (왼쪽 트리)가 노드를 반환하면 A와 B가 모두 왼쪽 트리에서 찾고 반환 된 노드가 최종 결과임을 알 수 있습니다. LCA (왼쪽)와 LCA (오른쪽)가 모두 비어 있지 않은 노드를 반환하면 A와 B가 각각 왼쪽과 오른쪽 트리에 있음을 의미합니다. 이 경우 루트 노드는 가장 낮은 공통 노드입니다.
자세한 분석 및 솔루션은 최저 공통 조상 을 확인하십시오 .
여기서 일부 솔루션은 루트 노드에 대한 참조가 있다고 가정하고 일부는 트리가 BST라고 가정합니다. root노드와 트리 를 참조하지 않고 해시 맵을 사용하여 솔루션을 공유하는 것은 BST 또는 비 BST 일 수 있습니다.
var leftParent : Node? = left
var rightParent : Node? = right
var map = [data : Node?]()
while leftParent != nil {
map[(leftParent?.data)!] = leftParent
leftParent = leftParent?.parent
}
while rightParent != nil {
if let common = map[(rightParent?.data)!] {
return common
}
rightParent = rightParent?.parent
}
해결 방법 1 : 재귀-더 빠름
- 아이디어는 루트에서 시작하여 나무를 횡단하는 것입니다. 주어진 키 p 및 q 중 하나가 root와 일치하면 root는 LCA이며 두 키가 모두 있다고 가정합니다. root가 어떤 키와도 일치하지 않으면 왼쪽 및 오른쪽 하위 트리를 반복합니다.
- 하나의 키가 왼쪽 서브 트리에 있고 다른 키가 오른쪽 서브 트리에있는 노드는 LCA입니다. 두 키가 모두 왼쪽 하위 트리에 있으면 왼쪽 하위 트리에도 LCA가 있고 그렇지 않으면 LCA가 오른쪽 하위 트리에 있습니다.
- 시간 복잡도 : O (n)
- 공간 복잡도 : O (h)-재귀 호출 스택
class Solution
{
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
if(root == null || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null)
return right;
else if(right == null)
return left;
else
return root; // If(left != null && right != null)
}
}
해결 방법 2 : 반복-부모 포인터 사용-느림
- 빈 해시 테이블을 만듭니다.
- p와 모든 조상을 해시 테이블에 삽입하십시오.
- q 또는 해당 조상 중 하나가 해시 테이블에 있는지 확인하고, 예인 경우 첫 번째 기존 조상을 리턴하십시오.
- 시간 복잡도 : O (n)-최악의 경우 이진 트리의 모든 노드를 방문 할 수 있습니다.
- 공간 복잡성 : O (n)-부모 포인터를 사용하는 공간 해시 테이블, 상위 항목 _ 세트 및 대기열은 각각 O (n)입니다.
class Solution
{
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
HashSet<TreeNode> ancestors_set = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
parent_map.put(root, null);
queue.add(root);
while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
{
TreeNode node = queue.poll();
if(node.left != null)
{
parent_map.put(node.left, node);
queue.add(node.left);
}
if(node.right != null)
{
parent_map.put(node.right, node);
queue.add(node.right);
}
}
while(p != null)
{
ancestors_set.add(p);
p = parent_map.get(p);
}
while(!ancestors_set.contains(q))
q = parent_map.get(q);
return q;
}
}
'Programing' 카테고리의 다른 글
| Java에서 마지막 N 개 요소를 보유하는 크기 제한 큐 (0) | 2020.05.18 |
|---|---|
| + PHP에서 배열 연산자? (0) | 2020.05.18 |
| bash에 "goto"문이 있습니까? (0) | 2020.05.18 |
| 앱 런처 아이콘에 알림 수를 표시하는 방법 (0) | 2020.05.18 |
| SQL Server 2005의 한 명령문에서 두 개의 테이블을 업데이트하는 방법은 무엇입니까? (0) | 2020.05.18 |