Leetcode608.树节点（中等）

题目
给定一个表 tree，id 是树节点的编号， p_id 是它父节点的 id 。

+----+------+
| 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' 是根节点，因为它的父节点是 NULL ，同时它有孩子节点 '2' 和 '3' 。
节点 '2' 是内部节点，因为它有父节点 '1' ，也有孩子节点 '4' 和 '5' 。
节点 '3', '4' 和 '5' 都是叶子节点，因为它们都有父节点同时没有孩子节点。
样例中树的形态如下：

             1
           /   \
         2       3         
       /   \
     4       5

注意

如果树中只有一个节点，你只需要输出它的根属性。

生成数据

CREATE TABLE tree(id INT,p_id INT);
 
INSERT INTO tree VALUES (1,NULL);
INSERT INTO tree VALUES (2,1);
INSERT INTO tree VALUES (3,1);
INSERT INTO tree VALUES (4,2);
INSERT INTO tree VALUES (5,2);

解答
最开始错误的尝试

SELECT T1.`id`, @Type:=IF(T3.`id` IS NOT NULL, 'Leaf', IF(T2.`id` IS NOT NULL, 'Inner', 'Root')) AS 'Type'
FROM tree AS T1
LEFT JOIN tree AS T2
ON T1.`p_id` = T2.`id`
LEFT JOIN tree AS T3
ON T2.`p_id` = T3.`id`

3应该是叶节点 这样是不对的

理解错了 p_id是父节点 应该T1.id = T2.p_id
重新连接三表

SELECT *
FROM tree AS T1
LEFT JOIN tree AS T2
ON T1.`id` = T2.`p_id`
LEFT JOIN tree AS T3
ON T2.`id` = T3.`p_id`

这样才对嘛 然后判断T1表p_id为空的一定为根节点 剩下T2中p_id不为空的一定是内部节点 否则就是叶节点

SELECT DISTINCT T1.`id`, @Type:=IF(T1.`p_id` IS NULL, 'Root', IF(T2.`p_id` IS NOT NULL, 'Inner', 'Leaf')) AS 'Type'
FROM tree AS T1
LEFT JOIN tree AS T2
ON T1.`id` = T2.`p_id`
LEFT JOIN tree AS T3
ON T2.`id` = T3.`p_id`;

哦了

然而 太菜 太天真

别的解法
父节点为NULL是根节点。

T.p_id is NULL

除去根节点，在父节点中出现过的是内部节点。

exists (
            select *
            from tree as T1
            where T1.p_id = T.id
)

其它的是叶子节点。

SELECT 
  T.`id`,
  IF(
    T.`p_id` IS NULL,
    'Root',
    IF(
      EXISTS 
      (SELECT 
        * 
      FROM
        tree AS T1 
      WHERE T1.p_id = T.`id`),
      'Inner',
      'Leaf'
    )
  ) AS 'Type'
FROM
  tree AS T ;

从id集合中，逐步排除掉根节点，叶节点，剩下的都是内节点

自连接一次即可

SELECT *
FROM tree AS T1 LEFT JOIN tree AS T2 ON (T1.id = T2.p_id)

显然T1.p_id为NULL的是根节点。

叶子节点的id不可能出现在p_id字段。因此T2.p_id为NULL的是叶子节点。
剩下的是内节点。

SELECT distinct T1.id,
if(T1.p_id IS NULL,
    'Root',
    if(T2.p_id IS NULL,
    'Leaf',
    'Inner'
    )
    ) AS `Type`
FROM tree AS T1 LEFT JOIN tree AS T2 ON (T1.id = T2.p_id)