LCA(Lowest Common Ancestor) 알고리즘이란? 두 개의 노드의 가장 가까운 공통된 부모를 찾는 알고리즘을 말한다. 어떻게 찾을 수 있을까? 위의 트리에서 9와 13의 공통 부모는 둘의 바로 위에 있는 2이다. 물론 9와 13과 같이 같은 Level에 있는 노드인 경우에 두 노드의 Level을 동시에 하나씩 줄여가며 찾을 수 있겠지만 만약 서로 다른 Level에 있는 경우 동시에 거슬러 올라간다 한들 공통 부모를 찾을 수 없다. 따라서 Level이 다른 경우에는 하나의 노드를 거슬러 올라가도록 하여 같은 Level로 맞춰줘야만 한다. 정리하자면, 더 깊은 Level에 있는 노드의 Level을 줄여 얕은 Level에 있는 노드와 동일하게 맞춰줘야 한다. Level과 부모 노드 구하기 우선 ..