608. 树节点（难度：中等）

题目描述

（通过次数37,772 | 提交次数60,037，通过率62.91%）

给定一个表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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/tree-node

--测试数据
Create table If Not Exists Tree (id int, p_id int);

insert into Tree (id, p_id) values ('1', 'None');
insert into Tree (id, p_id) values ('2', '1');
insert into Tree (id, p_id) values ('3', '1');
insert into Tree (id, p_id) values ('4', '2');
insert into Tree (id, p_id) values ('5', '2');

解题思路

源表Tree中保存了一颗树的所有节点，以及所有节点的父节点。

对于一个节点的属性，有无父节点、有无子节点，有以下可能的组合：


那么，我们可以计算出每一个节点的“有无父节点、有无子节点”这两个属性。然后根据属性的值，映射出对应的节点类型。

对于“有无父节点”，可以根据p_id的值是否为NULL来判断。

对于“有无子节点”，可以根据节点id是否存在于p_id列来判断。

因为所有节点只有三种类型，那么，我们可以分别计算出不同类型的节点，然后将计算结果合并。

也可以直接在SELECT查询中，根据对应的条件，判断出不同的节点类型，然后直接返回。

参考SQL

未特别说明的情况下，参考SQL为基于MySQL8.0实现。

select
    a.id,
    case when a.p_id is null then 'Root'
         when a.p_id is not null and exists (select 1 from tree b where a.id = b.p_id) then 'Inner'
         else 'Leaf'
    end Type
from tree a
order by a.id;