Binary Search Tree는 항상 부모 노드의 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽은 큰 값을 가지도록 설계되어져 있으므로, Binary Search Tree에서 LCA (Least Common Ancestor)는 두 값이 분기하는 노드가 LCA가 된다. 예를 들어 , 노드 4와 7의 LCA는 6이 된다. 노드 6과 4의 LCA는 6이 된다.
하지만, Binary Tree의 경우에는 이런 규칙이 없으므로, LCA를 찾기 위해 좀 더 복잡한 방법이 필요하다.
copied from http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/tree1.bmp
예를 들어 Node 1와 2의 LCA는 7이지만, Binary Search Tree에서 이용한 방법을 적용할 수 없다.
따라서, Binary Tree에서 LCA를 찾기 위한 다양한 방법을 인터넷에서 찾을 수 있다.
여기서 구현한 방법은 LinkedList를 이용하여 각 Node의 Path를 저장하고, LinkedList의 내용을 비교하면서 Node가 달라지는 시점을 LCA로 인식하는 방법이다.
예를 들어, Node 2와 12의 LCA를 구한다고 가정한다. 그러면, Node 12의 Path가 LinkedList에서 8->5->7->12로 저장되고, Node 2의 Path가 8->5->7->12->2로 저장된다.
두 개의 LinkedList의 값을 앞에서 부터 하나씩 비교해 나가면, 12 다음부터 두 Node의 Path가 변경됨을 인식함으로, LCA는 12가 된다.
아래 코드를 재귀 호출을 이용하여 각 Node Path를 찾고, Node Path를 비교하면서 LCA를 찾는 코드이다.
public static LinkedList findNode( Node root, int val ) {
// root가 null이면 null을 리턴
if( root==null )
return null;
// root의 값의 찾는 Node 값이면, LinkedList의 앞부분에 추가하고 리턴
LinkedList list = new LinkedList();
if( root.getValue()==val ) {
list.addFirst( root.getValue() );
return list;
}
// root노드의 자식 노드들이 모두 null이면, null을 리턴
if( root.getLeft()==null && root.getRight()==null )
return null;
// root의 왼쪽 Node 검색
if( root.getLeft()!=null ) {
list = findNode( root.getLeft(), val );
// 리턴 값이 null이 아니면 현재 Node 값을 LinkedList 앞에 추가
if( list!=null ) {
list.addFirst( root.getValue() );
return list;
}
}
if( root.getRight()!=null ) {
list = findNode( root.getRight(), val );
if( list!=null ) {
list.addFirst( root.getValue() );
return list;
}
}
return null;
}
public static void findLCA( Node root, int p, int q ) {
// root가 null 인지 확인
if( root==null )
System.out.println("Tree is empty");
// 각 Node의 Path를 저장하기 위한 2개의 LinkedList 생성
LinkedList
LinkedList
pathP = findNode( root, p );
pathQ = findNode( root, q );
// LinkedList가 Null인지 확인
if( pathP==null || pathQ==null ) {System.out.println( " Can't find LCA" );
return;
}
// iteration을 위한 값 설정
// 두 개의 LinkedList 중 size가 적은 것을 기준으로 iteration하면서 path 확인
int nSize = Math.min( pathP.size(), pathQ.size() );int LCA = -32767;
int pVal = -32767;
int qVal = -32767;
int i=0;
while( i
pVal = pathP.poll();
qVal = pathQ.poll();
// Path 값이 동일하면 LCA 값 Update
if( pVal==qVal )
LCA = pVal;
else
break;
i++;
}
if( LCA==-32767 )
System.out.println( " Can't find LCA" );
else
System.out.println( " LCA is " + LCA );
}
