专栏首页SQL实现SQL 二叉树节点

SQL 二叉树节点

这是一道在 HackerRank 上的 SQL 竞赛题,题目叫做“Binary Tree Nodes”,它的难度等级属于中级。

题目描述

给定一张表 BST,其中包含两列:N 和 P,其中 N 表示二叉树中节点的值,P 是 N 的父级。

Column

Type

N

Integer

P

Integer

编写 SQL 以查找按节点值排序的二叉树的节点类型。每个节点只能属于以下类型中的一种:

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

「输入样例」

N

P

1

2

3

2

6

8

9

8

2

5

8

5

5

null

「输出结果」

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

「说明」

下图是示例数据构成的二叉树:

解决方案

每个节点的类型只能属于 Root、Leaf、Inner 中的一种。Root 类型很好判断,如果一个节点没有父节点,那该节点就是根节点,对应的类型就是 Root。如果一个节点没有子节点,那么它就是叶子节点,即为 Leaf 类型。

除了 Root 和 Leaf 类型的节点,剩下的就是 Inner 类型的节点。该如何判断一个节点是不是 Inner 类型呢?

能不能通过“存在子节点”这个条件判断呢?不能!因为根节点也有子节点。

那通过“存在父节点”这个条件判断呢?也不能!因为叶子节点存在父节点。

显然,这两个条件的范围都太大了,我们适当加入一些限制条件就可以用来判断是不是 Inner 类型的节点了。“存在子节点且不为根节点”和“存在父节点且不为叶子节点”都可以用来作为判断节点是 Inner 类型的条件。

具体的 SQL(MySQL) 实现如下:

SELECT
  N,
  IF(
    P IS NULL,
    'Root',
    IF (
      (SELECT
        COUNT(*)
      FROM
        BST
      WHERE P = a.N) = 0,
      'Leaf',
      'Inner'
    )
  )
FROM
  BST a
ORDER BY N

本文分享自微信公众号 - SQL实现(gh_684ee9235a26),作者:zero

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SQL 的执行顺序

    了解 SQL 的执行顺序非常有价值,它可以让我们写出语法正确的 SQL,帮助我们简化编写新查询的过程。

    白日梦想家
  • SQL 找出 100 以内的质数

    之前我写了一篇文章 SQL 生成斐波那契数列,在原来的基础上,今天就来实现使用 SQL 获取 100 以内的质数。

    白日梦想家
  • 除了会排序,你对ORDER BY的用法可能一无所知!

    小伙伴们在进行SQL排序时,都能很自然的使用到ORDER BY。不管是默认ASC的升序,还是DESC降序,几乎都是信手拈来。

    白日梦想家
  • 关于BUS通信系统的一些思考(三)

    好久没写总结啦,最近一段时间比较忙,抽出的空闲时间都在不断完善之前提到的一个进程间通信lib的想法和实现(libatbus)。

    owent
  • 【LeetCode】每日一题(8.2)二叉树展开为链表

    具体做法是,对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点(其实就是找左子节点的最...

    看、未来
  • 数据结构与算法-树

    用户3470542
  • 最强大的GNN出现了!

    论文:https://arxiv.org/pdf/2009.00142.pdf 代码:https://github.com/snap-stanford/dist...

    Houye
  • Redis Cluster执行流程

    集群(cluster)是Redis提供的分布式数据库解决方案,集群通过分片(sharding)来进行数据共享,并提供数据复制(replication)和故障转移...

    张申傲
  • 小白初识Zookeeper

    首先,了解一个Zookeeper是什么,其是一个开源的分布式协调服务,分布式数据一致性的解决方案。

    Liusy
  • Redis底层数据结构详解

    上一篇说了Redis有五种数据类型,今天就来聊一下Redis底层的数据结构是什么样的。是这一周看了《redis设计与实现》一书,现来总结一下。(看书总是非常烦躁...

    Liusy

扫码关注云+社区

领取腾讯云代金券