리트코드 : 608. Tree Node

리트코드 : 608. Tree Node

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

---

문제

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.

문제 풀이

MySQL

WITH ROOT AS (
    SELECT ID
    FROM TREE
    WHERE P_ID IS NULL
    ),
    LEAF AS (
    SELECT ID
    FROM TREE
    WHERE ID NOT IN (SELECT P_ID FROM TREE WHERE P_ID IS NOT NULL)
    )

SELECT ID,
    CASE 
        WHEN ID IN (SELECT ID FROM ROOT) THEN 'Root'
        WHEN ID IN (SELECT ID FROM LEAF) THEN 'Leaf'
        ELSE 'Inner'
    END AS TYPE
FROM TREE

• 루트 노드는 부모 = NULL
• 리프 노드는 NULL이 아닌 애들 중에서, ID가 부모에 등장하지 않은 애들
  • NULL이 포함된 행에 NOT IN을 쓰니까 제대로 동작을 안한다.
• CASE WHEN문을 사용해서 컬럼 작성해주기.

Pandas

import pandas as pd


def tree_node(tree: pd.DataFrame) -> pd.DataFrame:

    root = tree[tree['p_id'].isnull()]
    root['type'] = 'Root'

    leaf = tree[(~tree['id'].isin(tree['p_id'])) & (~tree['id'].isin(root['id']))]
    leaf['type'] = 'Leaf'

    temp = pd.concat([root,leaf])
    answer = pd.merge(tree,temp, on='id', how='left')
    answer['type'].fillna('Inner', inplace=True)
    return answer[['id','type']]

• root, leaf를 각각 찾고 concat 시키기.
• left join을 해주면 null이 나오는데 이 자리는 inner로 채우는 자리.

코멘트

• 같은 방식으로 짜도 SQL이랑 pandas랑 동작속도 차이가 좀 있다.
  • row base, columns base 차이라서 그런듯