[코딩인터뷰 완전정복] 4.10 하위 트리 확인

Q : 두 개의 커다란 이진 트리 T1과 T2가 있다고 하자. T1이 T2보다 훨씬 크다고 했을 때, T2가 T1의 하위트리인지 판별하는 알고리즘을 만들라. T1 안에 있는 노드 n의 하위 트리가 T2와 동일하면, T2는 T1의 하위 트리다. 다시 말해, T1에서 노드 n의 아래쪽을 끊어 냈을 때 그 결과가 T2와 동일해야 한다.

 

T1이  T2보다 훨씬 크다는 조건이 있으므로, 우리는 큰 트리에서 작은 트리를 찾아내기만 하면 된다.

방법은 여러가지가 있겠지만, 가장 먼저 떠올린 것은 T1에서 T2의 루트노드와 같은 노드를 찾았을 때만, 그 하위트리를 조사하는 방법이다.

이때 시간 복잡도는 이론상 O(mn) 이다.

m은 T1의 노드의 갯수, n은 T2의 노드의 갯수이다.

T1과 T2의 비교과정중 차이점이 하나라도 있으면 탈출하기 때문에, 실제로는 더 빠를것이다.

 

알고리즘 작동방식

1. T1을 재귀적으로 순회하며 T2의 root노드와 일치하는 노드를 찾아낸다.

2. 찾아낸 트리와 T2가 일치하는지 확인한다.

3. 일치하면 True를 반환, 일치하지 않는다면 1번으로 돌아간다.

4. SubTree를 찾지 못하고 T1의 탐색이 끝나면 False를 반환.

// 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"

bool checkIsSameTree(TreeNode<int>* t1, TreeNode<int>* t2) {
	if (t1->data != t2->data) return false;
	if (t1->left != NULL) {
		if (t2->left == NULL) return false;
		if(!checkIsSameTree(t1->left, t2->left))
			return false;
	}
	else if (t2->left != NULL) return false;
	if (t1->right != NULL) {
		if (t2->right == NULL) return false;
		if (!checkIsSameTree(t1->right, t2->right))
			return false;
	}
	else if (t2->right != NULL) return false;

	return true;
}

bool findSubtree(TreeNode<int>* t1, TreeNode<int>* t2) { // t1 > t2
	if (t1->data == t2->data) 
		if(checkIsSameTree(t1, t2)) return true;
	if (t1->left != NULL) {
		if (findSubtree(t1->left, t2))
			return true;
	}
	if (t1->right != NULL) {
		if (findSubtree(t1->right, t2))
			return true;
	}
	return false;
}

int main() {
	TreeNode<int>* T1 = new TreeNode<int>(1);
	TreeNode<int>* T2 = new TreeNode<int>(2);

	T1->addLeft(2);
	T1->addRight(3);
	T1->left->addLeft(4);
	T1->left->addRight(5);
	T1->right->addLeft(6);

	T2->addLeft(4);
	T2->addRight(5);

	printf("%d\n", findSubtree(T1, T2));
}