在SQL中找到树节点

Question

嗨，最近在Uber中问了一个SQL问题，这确实很有趣，而且很难。

这个问题如下

表：tree

+-------------+------+
| 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