4.8 첫번째 공통 조상

문제 

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

 

해법

1. 부모노드에 대한 링크가 있는 경우

 - p와 q에서 시작해서 둘이 만날 때까지 위로 올라가면 된다. (교집합문제와 비슷한 방식)

 - p의 경로를 따라 올라가면서 q를 덮을 수 있는 노드인지 확인한다. 

   p의 부모의 본인이 아닌 다른쪽의 하위노드들을 검사하여 q가 있다면 그것이 첫번째 조상, 아니라면 그 위의 부모를 탐색하는 방식

 

2. 부모노드에 대한 링크가 없는 경우

 - p와 q가 어떤 노드로부터 둘다 오른쪽에 있다면 오른쪽으로 내려가서 공통 조상의 여부를 찾아야 한다. 더이상 같은 쪽에 있지 않다면 그 노드가 바로 공통조상이 될 것이다. 이 방식대로 구현한다면 O(N)시간으로 최적시간이 나오긴하지만, 반복연산이 있다. 왜냐하면 처음에 기주점으로부터 왼쪽에 n, 오른쪽에 n개 탐색을 하면 2n번의 탐색 후 오른쪽 또는 왼쪽으로 분기하여 다시 2n/2개의 노드에 대해 호출되고 그다음에는 2n/4 .. 그러다보면 결국 o(N) 시간이 걸리지만 반복적으로 탐색하는 부분을 줄일 수 있을 것 같다. 

 

- 반복적으로 탐색하는 것을 줄이기 위해서 

  > 루트의 하위 트리가 p(또는 q)를 포함하고 q(또는 p)를 포함하지 않으면 p(또는 q)를 반환.

  > p나 q가 루트의 하위트리 내에 없으면 null을 반환한다. 

  > 어느곳에도 해당사항이 없으면 p와 q의 공통조상을 반환한다. 

  이런식으로 한번의 탐색으로 이전 노드들에 대한 검색 결과를 거품처럼 띄워 올리는 방식으로 기본적인 로직은 첫번째와 차이가 없다. 

 

class result:
    def __init__(self, node, isAncestor):
        self.node = node
        self.isAncestor = isAncestor

def Solution(root, p, q):
    re = AncHelper(root, p, q)
    if re.isAncestor : return re.node
    else : return None

def AncHelper(root, p, q):
    if root is None :
        return None
    if root == p and root == q:
        return (p, True)

    rx = isAncestor(root.left, p, q)
    if rx.isAncestor :
        return rx
    ry = isAncestor(root.right, p, q)
    if ry.isAncestor :
        return ry
    if rx and ry:
        return result(root, True)
    elif root == p or root == q:
        isAncestor = rx is not None or ry is not None
        return result(root, isAncestor)
    else :
        return result(rx if rx is not None else ry , False)

위의 코드를 보면 result class를 생성한 것을 볼 수 있다. 이곳에는 node와 이 노드가 조상인지의 여부를 가지고 있다.

이 클레스는 두가지 문제를 해결해 줄 수 있다. 

1. p가 q의 자식 ( 또는 q가 p의 자식)인경우

2. p는 존재하지만 q는 존재하지 않는 경우 ( 또는 그반대의 경우)

이 두가지 경우를 구분해 내지 못한다. 

실제로 q가 p의 자식이라면 p를 반환하여 원하는 결과를 얻을 수 있겠지만, 자식인지를 확인하지 않고 그럴 것이라고 생각하고 반환해버리는 것이기 때문에 p는 존재하지만 q가 존재하지 않는 경우에도 p를 반환하여 원하지 않는 결과를 얻을 수 있다. 

따라서 IsAncestor 변수를 두어서 이것이 실제 조상인지에 대한 bool값이 필요했다.