4.10 하위 트리 확인

문제 

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

 

접근법

1. 순회를 통해 노드 안의 데이터들로 문자열을 만들고, T2의 문자열은 T1의 문자열의 부분 문자열이 된다. 

 - 어떤 순회를 해야할까에 대한 문제가 있다. 중위 순회를 한다고 했을때에는 이진탐색트리를 중위 순회 한다고 했을때 정렬된 값이 나온다고 했다. 그 말은 값은 같지만 구조가 다른 이진탐색트리에서는 같은 값이 나올 것이다. 전위 순회를 한다고 해보자. 전위 순회를 한다고 해도 문제가 있다. 루트노드가 3이고 왼쪽 하위노드가 4인경우와 루트노드가 3이고 오른쪽 하위노드가 4인 경우의 두 트리가 있다고 가정해보자. 그 경우에 둘다 전위순회를 하면 34 가 나올 것이다. 이것 또한 구조가 달라도 같은 결과 값이 나올 수 있음을 알 수 있다. 이 부분을 해결하기 위한 아이디어로는 Null 노드도 특정한 데이터로 대응시키는 것이다. Null을 X로 대응시킨다면 첫번째는 34X 두번째는 3X4로 다른 문자열이 만들어 질것이다. 

def Soution(T1, T2):
    str_t1 = getString(T1)
    str_t2 = getString(T2)
    return str_t1.find(str_t2) >= 0

def getString(root):
    if root is None:
        return "X"
    result = str(root.data) + getString(root.left) + getString(root.right)
    return result

이방식의 TimeComplexity = O(M+N) | Space Complexity = O(M+N)   [ M = T1의 노드수 |  N = T2의 노드수 ] 이다.

 

2. 큰 트리를 탐색하며 작은 트리와 같은 데이터를 발견할때마다 두 하위 트리가 동일한지 비교하는 함수를 호출한다.

def Soution(T1,T2):
    if T2 is None :
        return True
    return searchTree(T1,T2)

def searchTree(T1 , T2):
    if T1 is None :
        return False
    if T1.data == T2.data and matchTree(T1,T2):
        return True
    return searchTree(T1.left, T2) || searchTree(T1.right, T2)

def matchTree(T1,T2):
    if T1 is None and T2 is None :
        return True
    elif T1 is None or T2 is None :
        return False
    elif T1.data != T2.data :
        return False
    return matchTree(T1.right, T2.right) and matchTree(T1.left, T2.left)

단순히 이 방식의 TimeComplexity = O(MN)으로 생각 될 수 있다. 

하지만 T1의 모든노드에서 matchTree함수를 호출하는 것이 아니며, T2의 루트 노드값이 T1에 등장하는 빈도만큼(k)만 호출한다. 

또한, matchTree를 진행하는 순간중에서도 값이 같지 않으면 바로 종료해버리기 때문에 o(N + kM)에 가깝다고 할 수있다.

그리고 Space Complexity = O(logM + logN)이기 때문에 첫번째 방법에 비해 규모확장성 면에서 유리하다고 볼 수 있다.