43 树节点

[astak16]

题目

id  是树节点的编号， p_id  是它父节点的  id。

树中每个节点属于以下三种类型之一：

• 叶子：如果这个节点没有任何孩子节点。
• 根：如果这个节点是整棵树的根，即没有父节点。
• 内部节点：如果这个节点既不是叶子节点也不是根节点。

输出所有节点的编号和节点的类型，并将结果按照节点编号排序。根节点是 Root ，内部节点是 Inner，叶子节点是 Leaf

完整题目连接：树节点

create table tree (id int, p_id int)

insert into tree (id, p_id) values
(1, null),
(2, 1),
(3, 1),
(4, 2),
(5, 2);

分析

• p_id 是 null ，节点类型是 Root
• id 有对应的 p_id 节点类型是 Inner
• id 没有对应的 p_id 节点类型是 Leaf

SQL：方法一

select
	id,
	case
		when p_id is null then 'Root'
		when id in (select distinct p_id from tree) then 'Inner' else 'Leaf'
	end as type
from tree;

解析

• 使用 case ... when ... then ... end 判断 p_id 是不是 null ，如果是 null ，则是根节点 Root
• 查询出叶子节点的 id ， select p_id from tree
• 使用 in 操作符判断节点 id 在不在上一步的集合中，如果在则是内部节点 Inner，如果不在，则是叶子节点 Leaf

SQL：方法二

select
	id,
	if(isnull(p_id),
		'Root',
		if(id in (select distinct p_id from tree), 'Inner', 'Leaf')
	) as type
from tree;

解析

思路和方法一一样，这里是使用 if(..., ..., ...) 代替 case ... when ... then ... end 实现的。

方法三

select id, 'Root' as type from tree where p_id is null
union
select id, 'Inner' as type from tree where id in (
	select distinct p_id from tree where p_id is not null
) and p_id is not null
union
select id, 'Leaf' as type from tree where id not in (
	select distinct p_id from tree where p_id is not null
) and p_id is not null;

--- 等价于
with temp as (
	select distinct p_id from tree where p_id is not null
)
select id, 'Root' as type from tree where p_id is null
union
select id, 'Inner' as type from tree where id in (
	select p_id from temp
) and p_id is not null
union
select id, 'Leaf' as type from tree where id not in (
	select p_id from temp
) and p_id is not null;

解析

分别查询每一种节点，使用 union 将三种节点的结果连接起来

1. 查询根节点 Root，筛选条件是 p_id is null
2. 查询内部节点 Inner ，筛选条件是 id not in ( ... ) 里面是 p_id 的结果集 。并且 p_id is not null
3. 查询叶子节点 Leaf ，筛选条件是 id in ( ... ) 里面是 p_id 的结果集 。并且 p_id is not null
4. 最后使用 union 操作符将上面三步的结果连接起来

ps：那个方法是使用临时表将 p_id 的结果集 保存起来。