mysql之查询二叉树的根、叶子节点、分支节点_mysql 二叉树查询

问题

You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.
表结构

Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node:

• Root: If node is root node.
• Leaf: If node is leaf node.
• Inner: If node is neither root nor leaf node.

思考

刚开始也是没点头目，想着用左连接去一直连接到根，但题目并为告诉树的深度，所以此方法不可行，但是仔细思考会发现，叶子节点只会用一次，它还有父节点，分支节点会用多次，因为有叶子节点和父节点，而根节点没有父节点。
这一点在一次左连接之后可以清楚的观察到

也就是解题的关键，P为null，那么就是根节点，N中有，P中也有且不为null那就是分支节点，其他就是N中有，P中没有就是叶子节点

代码

SELECT N,
CASE
	WHEN
			P IS NULL THEN			'Root' 
			WHEN N  in (SELECT distinct P from bst where P is not null) THEN			'Inner' 
			ELSE 'Leaf' 
		END 
		FROM
			bst
		ORDER BY
			N
1
2
3
4
5
6
7
8
9
10
11