Skip to content

Latest commit

 

History

History
111 lines (85 loc) · 2.65 KB

File metadata and controls

111 lines (85 loc) · 2.65 KB
comments difficulty edit_url tags
true
中等
数据库

English Version

题目描述

表:Tree

+-------------+------+ 
| Column Name | Type | 
+-------------+------+ 
| N           | int  | 
| P           | int  |
+-------------+------+
N 是这张表中具有不同值的列。
每一行中包含 N 和 P,其中 N 表示二叉树中节点的值,P 是 N 的父亲。

编写一个解决方案来找到二进制树节点的类型。对于每个节点输出:

  • Root:如果节点是根节点。
  • Leaf:如果节点是叶子节点。
  • Inner: 如果节点既不是根节点,也不是叶子节点。

返回结果表,根据节点值 升序排序

结果格式如下所示。

 

示例 1:

输入:
Tree 表:
+---+------+
| N | P    | 
+---+------+
| 1 | 2    |
| 3 | 2    | 
| 6 | 8    | 
| 9 | 8    | 
| 2 | 5    | 
| 8 | 5    | 
| 5 | null | 
+---+------+
输出:
+---+-------+
| N | Type  | 
+---+-------+
| 1 | Leaf  | 
| 2 | Inner |
| 3 | Leaf  |
| 5 | Root  |
| 6 | Leaf  |
| 8 | Inner |
| 9 | Leaf  |    
+---+-------+
解释:
- 节点 5 是根节点,因为它没有父节点。
- 节点 1,3,6 和 8 是叶节点,因为它们没有任何子节点。
- 节点 2,4,7 是内部节点,因为它们充当结构中某些节点的父节点。

解法

方法一:左连接

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

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

MySQL

# 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;