遇到比较好玩的题型就想记录一下

题目

表：Tree

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id 是该表中具有唯一值的列。
该表的每行包含树中节点的 id 及其父节点的 id 信息。
给定的结构总是一个有效的树。

树中的每个节点可以是以下三种类型之一：

• “Leaf”：节点是叶子节点。
• “Root”：节点是树的根节点。
• “lnner”：节点既不是叶子节点也不是根节点。

编写一个解决方案来报告树中每个节点的类型。

思考过程

对于示例：

输入：
Tree table:
+----+------+
| 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. 无父节点：Root
2. 有父节点
   • 无子节点：Leaf
   • 有子节点：Inner

根据这个逻辑，很容易就能想到，通过id与p_id进行连接，即可得到每个节点的父节点和子节点

先给出直接将id与p_id连接(join)的结果与代码

select *  from Tree t1
join Tree t2 on t1.id  = t2.p_id

输入：

id	p_id
1	null
2	1
3	1
4	2
5	2

输出：

id	p_id	id	p_id
1	null	2	1
1	null	3	1
2	1	4	2
2	1	5	2

从上面的输出可以知道的是：第三列"id"为第一列"id"的子节点，那么上表中记录有，1节点有2和3两个子节点，2有4和5两个子节点

但是，问题在于如何准确的表达出3、4、5这三个节点的父节点、子节点的状态和个数

关键点：使用 LEFT JOIN ，当使用了LEFT JOIN后 会保留t1表的id 假如没有与之id匹配的p_id 那么右侧的p_id将为null

使用LEFT JOIN的SQL和结果（对第三列的id取名为c_id使得更加显而易见）：

select *  from Tree t1
left join Tree t2 on t1.id  = t2.p_id

| id | p_id | id   | p_id |
| -- | ---- | ---- | ---- |
| 1  | null | 3    | 1    |
| 1  | null | 2    | 1    |
| 2  | 1    | 5    | 2    |
| 2  | 1    | 4    | 2    |
| 3  | 1    | null | null |
| 4  | 2    | null | null |
| 5  | 2    | null | null |

稍加修改，就更加显而易见

select t1.id,t1.p_id,t2.id as c_id  from Tree t1
left join Tree t2 on t1.id  = t2.p_id

| id | p_id | c_id |
| -- | ---- | ---- |
| 1  | null | 3    |
| 1  | null | 2    |
| 2  | 1    | 5    |
| 2  | 1    | 4    |
| 3  | 1    | null |
| 4  | 2    | null |
| 5  | 2    | null |

那最后，就是对id进行 group by 统计每个id的p_id和c_id的数量，再根据判断逻辑编写 case when 解决问题~

题解

with pc as(
    select t1.id,t1.p_id,t2.id as c_id from Tree t1
    left join Tree t2 on t1.id  = t2.p_id
),
sta as (
    select id, count(p_id) as p_num,count(c_id) as c_num
    from pc
    group by id
)
select id,
case
    when p_num = 0 then 'Root'
    when p_num != 0 and c_num = 0 then 'Leaf'
    when p_num != 0 and c_num != 0 then 'Inner'
end as type
from sta