[LeetCode 608] 트리 노드의 타입 판별

URL : https://leetcode.com/problems/tree-node/description/

 

 

SQL 쿼리 관련 문제를 풀다가

재밌게 풀었던 문제가 있어 공유하고자 합니다.

트리의 노드를 분류하는 수많은 방법들이 있지만, 

여기서는 다음과 같은 분류법을 논하고 있습니다.

 

 

"해당 노드가 Root노드 인가, Leaf 노드 인가, 아니면 Inner 노드인가"

 

 

노드가 루트노드이려면 어떠한 특징을 가져야 하고,

잎사귀 노드이려면 어떠한 특징을 가져야 하고,

내부 노드이려면 어떠한 특징을 가져야 하는 지

생각해보고 정리할 수 있는 좋은 기회였습니다.

 

 

데이터가 다음과 같이 주어질 때에,

각 노드가  "Root", "Inner", "Leaf" 중에 어떠한 유형에 속하는 지 분류하는 문제입니다.

 

문제상황

 

즉, input이 위와 같이 주어졌을 때에 

output과 같은 모양으로 출력을 하면 성공입니다. 

이렇게 하려면 어떻게 쿼리문을 작성해야 할까요?

쿼리문을 작성하기 전에, 각 노드가 어떤 유형에 속하는 지 판별하기 위한 규칙을 먼저 공부해 봅시다.

 

각 노드가 어떠한 유형인지 판별하는 알고리즘

곰곰히 생각을 해 보니,

유형별로 다음과 같은 특징으로 정리가 되었습니다.

(이 문제에서 주어진 것은 각 노드의 부모노드이기에,

부모노드를 기준으로 하여 각 유형별 노드가 어떤 특징을 가져야 하는 지 정의한 것입니다!)

 

"어떤 노드가 Root Node이려면, 부모노드가 존재하지 않아야 한다"

"어떤 노드가 Inner Node이려면, 나를 부모로 가지는 노드가 하나 이상 존재하여야 한다."

"그 외에는 모드 Leaf Node이다."

 

이 규칙에 따라 SQL문을 작성하면 다음과 같이 됩니다.

select id, 
    (
    CASE
        WHEN p_id IS NULL THEN 'Root' // 부모노드가 null이라면 root노드
        WHEN id IN (select p_id from Tree) THEN 'Inner' // 나를 부모로하는 노드가 하나 이상이라면 Inner노드
        ELSE 'Leaf' // 그 이외에는 Leaf 노드
    END
    ) as 'type'
    from Tree;