[코딩인터뷰 완전정복] 4.8 첫 번째 공통 조상

Q : 이진 트리에서 노드 두개가 주어졌을 때 이 두 노드의 첫번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안 된다. 반드시 이진 탐색 트리일 필요는 없다.

 

1. brute force (무식한 방법)

한 노드의 조상들과 다른 노드의 조상들을 모두 비교해보면, 두 노드가 공통된 조상을 가지고 있는지 알아낼 수 있을 것이다. 우리는 두 노드의 첫번째 공통 조상을 찾아야 하기 때문에, 자식에서 부모순서로 탐색한다.

한 노드의 조상들을 다른 노드의 모든 조상 노드들과 비교하기 때문에 시간복잡도는 O(MN) 이다.

이때, M과 N은 각 노드의 조상 노드의 갯수이다.

 

임의의 노드 2개를 각각 A, B라고 하겠다.

A의 부모노드 A'과 B의 모든 부모노드들을 비교하여 A'가 A,B의 공통 조상인지 확인한다.

A'의 부모노드 A''과 B의 모든 부모노드들을 비교하여 A''가 A,B의 공통 조상인지 확인한다.

A,B의 공통 조상이 나올 때 까지 A의 부모노드를 하나씩 거슬러 올라가며 반복한다.

I의 부모 F와 H의 부모 E->C->A를 비교

F의 부모 D와 H의 부모 E->C->A를 비교

D의 부모 C와 H의 부모 E->C를 비교 후 C를 반환

2. depth 확인후 탐색

어떤 노드가 A,B 두 노드의 공통 조상이 되더라도, 그 노드의 depth는 정해져 있다.

따라서 A노드의 조상과 B노드의 조상중에 그 depth가 같은 것들 끼리만 비교를 한다면, 위의 방법보다 훨씬 빠르게 탐색을 할 수 있다.

이 방법의 시간 복잡도는 O(M+N)이다. (M과 N은 각 노드의 부모의 갯수)

 

A, B 노드에서 루트 노드까지 탐색하여 A와 B의 depth를 알아낸다.

depth가 높은 쪽이 낮은 쪽과 같아 질 때 까지 부모노드를 탐색하여 높이를 같게 한다.

각 노드의 부모를 추적하여 같은 노드인지 확인한다.

H와 I에서 root까지 탐색하여 깊이를 알아낸다.

깊이가 같아질 때 까지 높은 쪽을 탐색한다.

F의 부모 D와 H의 부모 E를 비교

D의 부모 C와 E의 부모 C를 비교 후 C를 반환

 

 

2번째 방법을 코드로 구현하였다.

//Node.h
template <class T>
class TreeNode{
public:
	T data;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;

	TreeNode(T data) {
		this->data = data;
	}

	void addLeft(TreeNode<T>* left) {
		this->left = left;
		left->parent = this;
	}

	void addLeft(T data) {
		TreeNode<T> *left = new TreeNode<T>(data);
		addLeft(left);
	}

	void addRight(TreeNode<T>* right) {
		this->right = right;
		right->parent = this;
	}

	void addRight(T data) {
		TreeNode<T> *right = new TreeNode<T>(data);
		addRight(right);
	}
};

#include <iostream>
#include "Node.h"

TreeNode<int>* findCommonAncester(TreeNode<int> *n1, TreeNode<int> *n2) {
	int n1_depth = 0, n2_depth = 0;
	TreeNode<int> *p, *q;
	p = n1;
	q = n2;

	while (p->parent != NULL) {
		n1_depth++;
		p = p->parent;
	}
	while (q->parent != NULL) {
		n2_depth++;
		q = q->parent;
	}

	p = n1;
	q = n2;

	if (n1_depth < n2_depth) {
		int temp = n1_depth;
		n1_depth = n2_depth;
		n2_depth = temp;

		p = n2;
		q = n1;
	}
	while (n1_depth != n2_depth) {
		n1_depth--;
		p = p->parent;
	}

	while (p != q) {
		if (p->parent == NULL) return NULL;
		p = p->parent;
		q = q->parent;
	}

	return p;
}

int main() {
	TreeNode<int> *a = new TreeNode<int>(1);
	a->addLeft(2);
	a->addRight(3);
	a->right->addLeft(4);
	a->right->addRight(5);
	a->right->right->addRight(8);
	TreeNode<int> *b = a->right->left;
	b->addLeft(6);
	b->addRight(7);
	b->left->addLeft(9);

	TreeNode<int> *p = b->left->left;
	TreeNode<int> *q = a->right->right->right;

	printf("%d\n", findCommonAncester(p, q)->data);
}