---

題目

有一個表BST，其中包含兩列：N和P，其中N表示二進制樹中節點的值，P是N的父級。

編寫一個查詢，以查找按節點值排序的二進制樹的節點類型。為每個節點輸出以下內容之一：
root：如果節點是根節點。
Leaf：如果節點是葉節點。
Inner：如果節點既不是根節點也不是葉節點。

輸入

輸出

1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

---

一、題析

根據上面題目可知

1. P 是 null，那對應的N就是 Root
2. 如果P和N中有對應的值，那 就是 Inner
3. 否則（P和N沒有值）就是 Leaf

二、題解

1.MySQL/SqlServer

代碼如下：

select DISTINCT a.N,
case when a.P is null then 'Root'
when b.P is null then 'Leaf' 
else 'Inner' end
from BST a left join  BST  b on a.N = b.P 
order by a.N

或者

SELECT BST.N, CASEWHEN BST.P IS NULL THEN 'Root' WHEN Parents.P IS NULL THEN 'Leaf'ELSE 'Inner' END
FROM BST
LEFT JOIN (SELECT DISTINCT P FROM BST ) Parents on Parents.P=BST.N
ORDER BY BST.N

2.Oracle

with tmp as (select n, p, level as lfrom   bstconnect by prior n = pstart with p is null
)
select n, case when l = 1 then 'Root'when l = (select max(l) from tmp) then 'Leaf'else 'Inner'end output
from tmp
order by n;

---