这是一道在 HackerRank 上的 SQL 竞赛题,题目叫做“Binary Tree Nodes”,它的难度等级属于中级。
给定一张表 BST,其中包含两列:N 和 P,其中 N 表示二叉树中节点的值,P 是 N 的父级。
Column | Type |
---|---|
N | Integer |
P | Integer |
编写 SQL 以查找按节点值排序的二叉树的节点类型。每个节点只能属于以下类型中的一种:
「输入样例」
N | P |
---|---|
1 | 2 |
3 | 2 |
6 | 8 |
9 | 8 |
2 | 5 |
8 | 5 |
5 | null |
「输出结果」
1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf
「说明」
下图是示例数据构成的二叉树:
每个节点的类型只能属于 Root、Leaf、Inner 中的一种。Root 类型很好判断,如果一个节点没有父节点,那该节点就是根节点,对应的类型就是 Root。如果一个节点没有子节点,那么它就是叶子节点,即为 Leaf 类型。
除了 Root 和 Leaf 类型的节点,剩下的就是 Inner 类型的节点。该如何判断一个节点是不是 Inner 类型呢?
能不能通过“存在子节点”这个条件判断呢?不能!因为根节点也有子节点。
那通过“存在父节点”这个条件判断呢?也不能!因为叶子节点存在父节点。
显然,这两个条件的范围都太大了,我们适当加入一些限制条件就可以用来判断是不是 Inner 类型的节点了。“存在子节点且不为根节点”和“存在父节点且不为叶子节点”都可以用来作为判断节点是 Inner 类型的条件。
具体的 SQL(MySQL) 实现如下:
SELECT
N,
IF(
P IS NULL,
'Root',
IF (
(SELECT
COUNT(*)
FROM
BST
WHERE P = a.N) = 0,
'Leaf',
'Inner'
)
)
FROM
BST a
ORDER BY N