Question

3054. Binary Tree Nodes

English Version

题目描述

Table: Tree

+-------------+------+ 
| Column Name | Type | 
+-------------+------+ 
| N       | int  | 
| P       | int  |
+-------------+------+
N is the column of unique values for this table.
Each row includes N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Write a solution to find the node type of the Binary Tree. Output one of the following for each node:

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

Return _the result table ordered by node value in ascending order_.

The result format is in the following example.

 

Example 1:

Input: 
Tree table:
+---+------+
| N | P  | 
+---+------+
| 1 | 2  |
| 3 | 2  | 
| 6 | 8  | 
| 9 | 8  | 
| 2 | 5  | 
| 8 | 5  | 
| 5 | null | 
+---+------+
Output: 
+---+-------+
| N | Type  | 
+---+-------+
| 1 | Leaf  | 
| 2 | Inner |
| 3 | Leaf  |
| 5 | Root  |
| 6 | Leaf  |
| 8 | Inner |
| 9 | Leaf  |  
+---+-------+
Explanation: 
- Node 5 is the root node since it has no parent node.
- Nodes 1, 3, 6, and 8 are leaf nodes because they don't have any child nodes.
- Nodes 2, 4, and 7 are inner nodes as they serve as parents to some of the nodes in the structure.

解法

方法一：左连接

如果一个节点的父节点为空，则它是根节点；如果一个节点不是任何节点的父节点，则它是叶子节点；否则它是内部节点。

因此，我们使用左连接来连接两次 Tree 表，连接条件是 t1.N = t2.P。那么如果 t1.P 为空，则 t1.N 是根节点；如果 t2.P 为空，则 t1.N 是叶子节点；否则 t1.N 是内部节点。

# Write your MySQL query statement below
SELECT DISTINCT
  t1.N AS N,
  IF(t1.P IS NULL, 'Root', IF(t2.P IS NULL, 'Leaf', 'Inner')) AS Type
FROM
  Tree AS t1
  LEFT JOIN Tree AS t2 ON t1.N = t2.p
ORDER BY 1;