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

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


퀴즈 질문


예상답변/설명

이진검색트리(Binary Search Tree)는 왼쪽 자식들이 부모 노드값보다 작고, 오른쪽 자식들이 부모 노드보다 크며, 중복된 값을 허용하지 않는다. 이러한 성질을 이용하여 재귀호출을 하면서, 왼쪽 자식들의 최대를 부모노드로, 오른쪽 자식들의 최소를 부모노드로 다시 지정하면서 자식노드들의 범위를 체크한다.

public static bool IsBst(Node root)
{
    var minNode = root;
    while(minNode.Left != null)
    {
        minNode = minNode.Left;
    }

    var maxNode = root;
    while(maxNode.Right != null)
    {
        maxNode = maxNode.Right;
    }

    return IsBst(root, minNode.Key, maxNode.Key);
}

public static bool IsBst(Node node, int min, int max)
{
    if (node == null) return true;

    if (node.Key < min || node.Key > max)
    {
        return false;
    }

    return IsBst(node.Left, min, node.Key)   // Left노드의 최대는 현재노드
	    && IsBst(node.Right, node.Key, max); // Right노드의 최소는 현재노드
}