C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

먼저 문제에서 이진트리라고 명시한 것에 주의해야 한다. (만약 이진 검색 트리(Binary Search Tree, BST)인 경우, BST만이 갖는 특성을 살려 좀 더 간단히 구할 수 있다)

아래는 Recursive 함수를 사용한 예로서, 베이스 케이스(base case)로서 루트노드가 두개중 하나의 노드와 같으면 해당 루트노드가 최소 공통 부모가 되고, 만약 이 base case가 아니면, 좌우 노드를 다시 서브트리의 루트로 지정하고 Recursive 호출을 한다. 호출 결과 만약 좌우 결과가 모두 NULL이 아니면, 양쪽에 있다는 뜻이므로 현재 루트노드가 최소 공통이 되고, 왼쪽에만 NULL이 아니면, 두개가 모두 왼쪽에 있다는 뜻이고, 리턴 left 노드를 리턴한다. 물론 오른쪽도 같은 방식이다.

public TreeNode FindLCA(TreeNode root, TreeNode n1, TreeNode n2)
{
    if (root == null) return null;

    if (root == n1 || root == n2) return root;

    TreeNode left = FindLCA(root.Left, n1, n2);
    TreeNode right = FindLCA(root.Right, n1, n2);

    if (left != null && right != null) return root;
    if (left != null) return left;
    if (right != null) return right;

    return null;
}

또 다른 해법으로, 이진트리에 대해 InOrder Traversal과 PostOrder Traversal을 진행하여, InOrder에서 해당 두 노드값 사이에 있는 값들 중에서, PostOrder에서 가장 마지막에 있는 값을 찾아 리턴한다. 예를 들어, InOrder가 4,2,5,1,6,3,7 이고, PostOrder가 4,5,2,6,7,3,1 인 경우, 노드 5와 3의 최소 공통 부모는 InOrder에서 1,6을 발견하고, 다시 이 숫자들중 PostOrder에서 3보다 더 뒤에 있는 숫자 즉 1이 최소 공통이 된다. 이는 InOrder가 특성상 루트 노드를 중간에 있게 하고, PostOrder가 특성상 루트노드를 제일 마지막에 두는 까닭이다.