LeetCode 코딩 테스트 - Tree Node(LV.Medium)

 

 

Table: Tree

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id is the column with unique values for this table.
Each row of this table contains information about the id of a node and the id of its parent node in a tree.
The given structure is always a valid tree.

 

Each node in the tree can be one of three types:

• "Leaf": if the node is a leaf node.
• "Root": if the node is the root of the tree.
• "Inner": If the node is neither a leaf node nor a root node.

Write a solution to report the type of each node in the tree.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+
Output: 
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
| 2  | Inner |
| 3  | Leaf  |
| 4  | Leaf  |
| 5  | Leaf  |
+----+-------+
Explanation: 
Node 1 is the root node because its parent node is null and it has child nodes 2 and 3.
Node 2 is an inner node because it has parent node 1 and child node 4 and 5.
Nodes 3, 4, and 5 are leaf nodes because they have parent nodes and they do not have child nodes.

Example 2:

Input: 
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
+----+------+
Output: 
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
+----+-------+
Explanation: If there is only one node on the tree, you only need to output its root attributes.

 

테이블: Tree

+-------------+------+
| Column Name | Type |
+-------------+------+
| id | int |
| p_id | int |
+-------------+------+

• id는 이 테이블에서 고유한 값을 갖는 열입니다.
• 각 행은 트리에서 하나의 노드 ID와 해당 노드의 부모 노드 ID에 대한 정보를 포함합니다.
• 주어진 구조는 항상 유효한 트리입니다.

각 노드는 다음 세 가지 유형 중 하나일 수 있습니다.

• "Leaf": 리프 노드인 경우
• "Root": 루트 노드인 경우
• "Inner": 루트도 아니고 리프도 아닌 경우

각 노드의 유형을 반환하는 SQL 쿼리를 작성하세요.

---

예제 1

입력:

Tree 테이블:
+----+------+
| id | p_id |
+----+------+
| 1 | null |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
+----+------+

출력:

+----+-------+
| id | type |
+----+-------+
| 1 | Root |
| 2 | Inner |
| 3 | Leaf |
| 4 | Leaf |
| 5 | Leaf |
+----+-------+

설명:

• 노드 1은 p_id가 null이므로 루트 노드입니다. (자식 노드 2, 3이 있음)
• 노드 2는 부모 노드 1이 있고, 자식 노드 4, 5가 있으므로 내부 노드입니다.
• 노드 3, 4, 5는 부모 노드가 있지만 자식 노드가 없으므로 리프 노드입니다.

---

예제 2

입력:

Tree 테이블:
+----+------+
| id | p_id |
+----+------+
| 1 | null |
+----+------+

출력:

+----+-------+
| id | type |
+----+-------+
| 1 | Root |
+----+-------+

설명:

트리에 단 하나의 노드만 있는 경우, 해당 노드는 루트 노드입니다.

 

SELECT
    id,
    CASE
        # 1. p_id(부모노드의 id)가 null이면 'Root'노드
        WHEN p_id IS NULL THEN 'Root'
        # 2. 부모노드가 존재하고(어떤노드의 id가 본인의 p_id), 본인의 id가 어떤노드의 p_id 이면 'Inner' 
        WHEN p_id IN (SELECT id FROM tree) AND id IN (SELECT p_id FROM tree) THEN 'Inner'
        # 3. 아무것도 속하지 않으면 'Leaf'
        ELSE 'Leaf'
    END AS type
FROM tree