请教一道SQL题，OA遇到了，做不起然后挂了

表结构： ID，left，right，value
比如        1      4      3       Null
这个表可以代表一个二叉树，请找出ID为2的所有子节点（子节点的意思是儿子，孙子，曾孙子，曾曾孙子.....）的ID 和 value
网上也查过答案，但是没有二叉树结构的，完全不知道怎么写，有没有大神帮忙看看？非常谢谢
（公司是sevone， 我们学校旁边的小公司，new grad entry level）


补充内容 (2019-5-14 13:28):
要求用MySQL实现，就是非递归，请教各位大大有啥办法不

sql考这种题目和ppt做炫酷动画有什么区别,不知道出题人怎么想的,如果是面试的话我建议你直接怼他这个表的设计有问题

感觉declarative sql实现不了递归查询，imperative sql可以

恩，谢谢，不过要求是只能mysql，我只想到非递归，看网上有用left join，不过要知道树的深度

MySQL 8.0以上的话可以用递归：https://www.db-fiddle.com/f/uUcRiwK7S5vxKGMi9iaVG6/1

1. WITH RECURSIVE Descendents(ID, `left`, `right`, value) AS (
   
2.   SELECT * FROM BinaryTree WHERE ID = 2
   
3.   UNION ALL
   
4.   SELECT b.* FROM BinaryTree b, Descendents d
   
5.   WHERE b.ID = d.`left` OR b.ID = d.`right`
   
6. )
   
7. SELECT ID, value FROM Descendents
   
8. WHERE ID <> 2;

复制代码

MySQL 5.7以下版本的话就很hacky了，效率也低，只能算是做题游戏吧.. 可以这样写：https://www.db-fiddle.com/f/gncJDmCfyjktvPDhHQzZN5/3

1. SELECT DISTINCT b.ID, b.value
   
2. FROM BinaryTree b, BinaryTree,
   
3.      ( SELECT @pv := '2' ) INITIALIZATION
   
4. WHERE find_in_set(b.ID, @pv)
   
5. AND length(@pv := concat(@pv,
   
6.                          coalesce(concat(',', b.`left`), ''),
   
7.                          coalesce(concat(',', b.`right`), '')));
   

复制代码

主要是利用self join构造了一个双重循环，然后维护一个ID集合@pv

stack overflow上的答案 ( https://stackoverflow.com/questi ... cal-recursive-query ) 没有self join，其假设是ID大小构成了一个拓扑序（比如说子节点ID一定小于父节点ID）。如果我们想要摆脱这个限制，就需要用双重循环 —— 注意到外循环次数等于表中节点数量，必然是大于树的高度的。

补充内容 (2019-5-15 00:02):
PS：第二个query里面的"INITIALIZATION"不是提供什么特殊机制的关键字，只是表的alias，具体机制可以参见stack overflow链接里相关答案的解释

lyft 也考过类似题目，我赞同楼上，表设计成这样没问题，但是要求这么查询 而且设计成这样是不是傻

hubingcheng 发表于 2019-5-14 16:17
sql考这种题目和ppt做炫酷动画有什么区别,不知道出题人怎么想的,如果是面试的话我建议你直接怼他这个表的设 ...

说的对 我觉得 如果只是SDE的职位 真的没有必要考这么难的 DBA另说

补充内容 (2019-5-14 21:37):
我个人的观点是 太偏的题 如果感兴趣看一看是可以的 一般准备面试的时候没必要看这种题 容易把自己带跑偏了 我们不可能取悦所有的面试官 尤其是那些奇葩的

magicsets 发表于 2019-5-14 16:13
MySQL 8.0以上的话可以用递归：https://www.db-fiddle.com/f/uUcRiwK7S5vxKGMi9iaVG6/1

[mw_shl_code=sq ...

谢谢大神！

SQL很早就有recursive query了 （https://en.wikipedia.org/wiki/Hi ... sive_queries_in_SQL），专门来解决这一类的问题。
另外SQL本身是个turing complete的语言，别的编程语言能实现的功能都能用SQL实现。。。

感觉SQL就不适合干这样的事吧
别的CODE可能很快就写出来了，SQL不太有效率吧