[Coding Interview] 트리 관련 문제

 

문제 : 수백개의 노드로 구성된 이진 트리 A 가 있고, 수십개의 노드로 구성된 이진 트리 B가 있다.   트리 B가 트리 A의 하위트리인지 아닌지 판별하라.   (트리 A에서 어떤 노드 n을 끊어냈을 때 트리 B가 생기면, 트리 B는 트리 A의 하위노드라고 한다.)   만약 참조값에 따라 트리가 정의된다면, 트리 B의 root 노드의 참조값을 트리 A가 갖고 있을 때 true 를 반환하면 된다. 트리 A를 순회하는 방법은 이진트리답게 그냥 return (left~ || right~) 해도 되고, 그냥 DFS, BFS 를 사용해도 될 것이다.   만약 참조값에 따라 트리가 정의되지 않고, "노드들의 값이 같은 것으로" 트리가 정의된다면, 아래처럼 다른 방법을 써야 할 것이다.   첫번째 풀이 : 트리 A,B 모두 in-order(전순회)나 pre-order(정순회)로 String을 만든 후 트리 A의 String 에 트리 B의 String 이 부분 String 인지 판별해본다.   두번째 풀이 : 트리 B 를 in-order(전순회)나 pre-order(정순회)로 String을 만든다. 트리 A를 순회하다가, 트리 B root 노드의 값과 똑같은 노드를 만나면, 거기서부터 트리 A를 in-order 혹은 pre-order String 을 만들어 미리 만들어둔 트리 B의 String과 비교한다.   세번째 풀이 : 트리 A를 순회하다가, 트리 B root 노드의 값을 만나면(이걸 노드 n 이라고 하자), 위처럼 String 을 만드는 대신, 트리 간 서로 노드를 비교한다.  노드 n 과 트리 B의 root 노드를 인자로 갖는 재귀함수를 만들어서, 만약 값이 같다면 n.left와 root.left 를 재귀함수의 인자로 넣고, n.right 와 root.right 를 재귀함수의 인자로 넣는다. return 값은 boolean (같으면 true, 틀리면 false) 이고 최종적으로 처음 함수의 값이 true 라면 트리 B의 하위 트리가 트리 A라고 말할 수 있겠다. 이 때 마지막 leaf 노드나 다음 노드가 null 일 때 상황을 잘 처리해야겠다.   세번째 방법처럼 풀면 O(n + km) 의 시간이 걸린다(크게 봐서 O(nm)) n은 트리 A의 모든 노드를 순회하는 값이고, k는 트리 A를 순회할 때 트리 B의 root 노드 값과 같은 노드를 만나는 횟수 m은 트리 B의 모든 노드 수이다. 즉 km은, 트리 A가 트리 B의 root 노드 값과 같은 노드를 만날 때마다(k번 만날 것임) 두 트리를 비교하는(최대 m만큼) 데 걸리는 시간이다. (사실 비교하면서 틀린 부분이 있다면 바로 멈출 것이고, k 만큼 찾기 전에 끝날 수 있으므로 O(n+km)는 최악의 시간을 의미하고, 평균적으로 더 적은 시간이 걸린다.)