|
| 1 | +--608. Tree Node |
| 2 | +--Given a table tree, id is identifier of the tree node and p_id is its parent node's id. |
| 3 | +-- |
| 4 | +--+----+------+ |
| 5 | +--| id | p_id | |
| 6 | +--+----+------+ |
| 7 | +--| 1 | null | |
| 8 | +--| 2 | 1 | |
| 9 | +--| 3 | 1 | |
| 10 | +--| 4 | 2 | |
| 11 | +--| 5 | 2 | |
| 12 | +--+----+------+ |
| 13 | +--Each node in the tree can be one of three types: |
| 14 | +--Leaf: if the node is a leaf node. |
| 15 | +--Root: if the node is the root of the tree. |
| 16 | +--Inner: If the node is neither a leaf node nor a root node. |
| 17 | +--Write a query to print the node id and the type of the node. Sort your output by the node id. The result for the above sample is: |
| 18 | +--+----+------+ |
| 19 | +--| id | Type | |
| 20 | +--+----+------+ |
| 21 | +--| 1 | Root | |
| 22 | +--| 2 | Inner| |
| 23 | +--| 3 | Leaf | |
| 24 | +--| 4 | Leaf | |
| 25 | +--| 5 | Leaf | |
| 26 | +--+----+------+ |
| 27 | +--Explanation |
| 28 | +-- |
| 29 | +--Node '1' is root node, because its parent node is NULL and it has child node '2' and '3'. |
| 30 | +--Node '2' is inner node, because it has parent node '1' and child node '4' and '5'. |
| 31 | +--Node '3', '4' and '5' is Leaf node, because they have parent node and they don't have child node. |
| 32 | +-- |
| 33 | +--And here is the image of the sample tree as below: |
| 34 | +-- 1 |
| 35 | +--/ \ |
| 36 | +-- 2 3 |
| 37 | +-- / \ |
| 38 | +-- 4 5 |
| 39 | +--Note |
| 40 | +-- |
| 41 | +--If there is only one node on the tree, you only need to output its root attributes. |
| 42 | + |
| 43 | +--credit: https://leetcode.com/articles/tree-node/#approach-i-using-union-accepted |
| 44 | +select id,'Root'as Typefrom treewhere p_id isnull |
| 45 | +union |
| 46 | +select id,'Leaf'as Typefrom treewhere id notin |
| 47 | + (select distinct p_idfrom tree |
| 48 | +where p_idis not null) |
| 49 | +and p_idis not null |
| 50 | +union |
| 51 | +select id,'Inner'as Typefrom treewhere idin |
| 52 | + (select distinct p_idfrom tree |
| 53 | +where p_idis not null) |
| 54 | +and p_idis not null |
| 55 | +order by id; |