LeetCode MySQL-608. Tree Node

    AllenLi
    LeetCode MySQL

    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 an SQL query to report the type of each node in the tree.
    Return the result table ordered by id in ascending order.

    寫一個 SQL Query來報告樹(葉子、根、不是葉也不是根)之中，每一個節點的類型
依照 id 來排序結果。

    Table: Tree

    +-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id is the primary key column 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.

    Example 1:
    treeExample1

    Input: 
Tree1 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:
    treeExample2

    Input: 
Tree2 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.

    Solution:
    1. 選擇標題 id。
    2. 選擇標題 Type
    – 當 p_id 是 NULL 時，顯示 Root。
    – 當 id 在 Tree 表格中過濾與 p_id 重複的值，顯示 Inner。
    – 當不符合以上狀況時，顯示 Leaf。
    3. 來自 Tree 的 table。

    Code.1-1:

    SELECT 
	id,
    (CASE WHEN(p_id IS NULL) THEN 'Root'
	WHEN id IN(SELECT DISTINCT p_id FROM Tree1) THEN 'Inner'
        ELSE 'Leaf' END) AS Type
FROM Tree1;

    Code.1-2:

    SELECT 
        id,
	IF(ISNULL(p_id),'Root',IF(id IN(SELECT DISTINCT p_id FROM Tree),'Inner','Leaf')) AS Type
    FROM Tree
    ORDER BY id;

    newTreeTable1

    Code.2:
    SELECT
    id,
    (CASE WHEN(p_id IS NULL) THEN ‘Root’
    WHEN id IN(SELECT DISTINCT p_id FROM Tree2) THEN ‘Inner’
    ELSE ‘Leaf’ END) AS Type
    FROM Tree2;

    newTreeTable2

    Related Posts