我使用 "NOT IN" 正确吗？

Question

我正在尝试链接 here 的 HackerRank 问题。

我很好奇为什么我尝试的解决方案没有 return 二叉树叶子的任何行。这是我的完整查询：

SELECT N, 'Root'
FROM BST
WHERE ISNULL(P)

UNION

SELECT N, 'Inner'
FROM BST
WHERE N IN (SELECT P FROM BST) AND NOT ISNULL(P)

UNION

SELECT N, 'Leaf'
FROM BST
WHERE N NOT IN (SELECT P FROM BST)

ORDER BY N

在我看来，我识别叶子的方法是正确的——叶子被定义为不是父节点的节点。但是，当我单独尝试 SELECT N, 'Leaf' ... 查询时，我没有得到任何输出。

谁能发现我的错误？我是否正确使用了 NOT IN 语句？

编辑：澄清一下，N是节点的值，对应的P是它的父节点。 N和P都是整数。

Answer 1

您可以使用 case 表达式：

select n, 
    case when p is null then 'root'
         when not exists (select 1 from bst b1 where b1.p = b.n) then 'leaf'
         else 'inner'
    end as res
from bst b

这句话为：

如果 p 是 null，该节点没有父节点，因此它是一个（？）根节点
如果不存在p等于当前节点n的节点，则该节点没有子节点：是叶子
否则为内节点

请注意，至少在理论上，一个节点可以同时是根和叶；挑战问题没有提到这种可能性。如果发生这种情况，查询会将其标记为根（因为这是在 case 表达式中匹配的第一个分支）。

Answer 2

如果您运行叶查询，您将一无所获：

mysql> select n, 'Leaf' from bst where n not in (select p from bst);
Empty set (0.00 sec)

原因是子查询的结果包含NULL:

mysql> select distinct p from bst;
+------+
| p    |
+------+
| NULL |
|    1 |
|    3 |
|    4 |
+------+

比较 N not in (NULL, 1, 3, 4) 绑定到 return 没有匹配项，因为 NULL。这相当于：

WHERE NOT (N = NULL OR N = 1 OR N = 3 OR N = 4)

但是与 NULL 的任何比较都是 NULL，而不是 false。您可以获得 true/false 其他条款，但不是第一个条款。这简化为：

WHERE NOT (NULL OR FALSE OR FALSE OR FALSE)

这又简化为：

WHERE NOT (NULL)

但是NULL的否定也是NULL，不成立。因此，您查询中的条件必然会阻止所有节点，无论它们是否是叶子。

您可以通过消除 NULL 来解决此问题：

mysql> select n, 'Leaf' from bst where n not in (select p from bst where not isnull(p));
+---+------+
| n | Leaf |
+---+------+
| 2 | Leaf |
| 5 | Leaf |
| 6 | Leaf |
+---+------+

如果您有此类数据，您还应该考虑使用 recursive CTE queries in MySQL 8.0：

WITH RECURSIVE cte (N, Label) AS
( 
  SELECT bst.N, CAST('Root' AS CHAR(20)) FROM bst WHERE ISNULL(P)
  UNION ALL
  SELECT bst.N, IF(below.P IS NULL, 'Leaf', 'Inner') FROM bst JOIN cte ON bst.P=cte.N
  LEFT OUTER JOIN bst AS below ON bst.N=below.P
)
SELECT DISTINCT N, Label FROM cte

+------+-------+
| N    | Label |
+------+-------+
|    1 | Root  |
|    2 | Leaf  |
|    3 | Inner |
|    4 | Inner |
|    5 | Leaf  |
|    6 | Leaf  |
+------+-------+

我使用 "NOT IN" 正确吗？

Am I using "NOT IN" correctly?

mysql

sql

subquery

case

hierarchical-data