在SQL中查找树节点

Question

您好，最近在 Uber 上问了一个 sql 问题，这非常有趣，但也有点难。

问题如下

表：树

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| p_id        | int  |
+-------------+------+
id is the primary key column for this table.
Each row of this table contains information about the id of a node and the id of its parent node in a tree.
The given structure is always a valid tree.


[![Each node in the tree can be one of three types:

"Leaf": if the node is a leaf node.
"Root": if the node is the root of the tree.
"Inner": If the node is neither a leaf node nor a root node.
Write an SQL query to report the type of each node in the tree.

Return the result table ordered by id in ascending order.

The query result format is in the following example.][1]][1]

示例1

    Input: 
Tree table:
+----+------+
| id | p_id |
+----+------+
| 1  | null |
| 2  | 1    |
| 3  | 1    |
| 4  | 2    |
| 5  | 2    |
+----+------+
Output: 
+----+-------+
| id | type  |
+----+-------+
| 1  | Root  |
| 2  | Inner |
| 3  | Leaf  |
| 4  | Leaf  |
| 5  | Leaf  |
+----+-------+
Explanation: 
Node 1 is the root node because its parent node is null and it has child nodes 2 and 3.
Node 2 is an inner node because it has parent node 1 and child node 4 and 5.
Nodes 3, 4, and 5 are leaf nodes because they have parent nodes and they do not have child nodes.

现在我已经给出了答案，但我想用其他一些方法得到相同的结果，如果有的话请帮助我解决此类问题的其他方法

Answer 1

您也可以使用联接

select distinct a.id,
   case when a.p_id is null then 'root'
        when b.id is null then 'leaf'
        else 'inner' end node_type
from tree a
left join tree b on a.id = b.p_id
order by a.id

Answer 2

SELECT id, p_id 
, case when p_id is null then "root"
     when p_id is not null and id in (select distinct p_id from tree) then "Inner"
     else "Leaf"
end as type
from tree

Answer 3

您可以使用递归和交叉应用来获取 n 个输入的结果

;WITH RECTREE(id, p_id, type)
AS (
SELECT id, p_id, CONVERT(NVARCHAR(20),'Root') type FROM #TABLE WHERE p_id is null 
UNION ALL
SELECT B.id, B.p_id, CONVERT(NVARCHAR(20),Null) type FROM RECTREE A
INNER JOIN #TABLE B ON B.p_id = A.id
)
SELECT A.id, A.p_id, ISNULL(A.type, NodeChecker.Type) FROM RECTREE A
CROSS APPLY (SELECT TOP 1 CASE WHEN #TABLE.p_id > 0 THEN 'Inner' ELSE 'Node' END Type FROM RECTREE
LEFT JOIN #TABLE ON RECTREE.id = #TABLE.p_id WHERE A.id = RECTREE.id ORDER BY ISNULL(#TABLE.p_id, 0) ASC) NodeChecker