有人能解释一下 HackerRank 二叉树节点问题的解决方案吗？

Question

SELECT N, CASE WHEN P IS NULL THEN 'Root' 
WHEN(SELECT COUNT(*) FROM BST WHERE P = b.N) > 0 THEN 'Inner'
ELSE 'Leaf'
END
FROM bst b 
ORDER BY N;`

能否有人解释一下Hacker Rank二叉树节点问题的解决方案？为什么要使用p=b.n，如果我使用from bst和p=bst.n而不是from bst b和p=b.n会出现什么问题？

- Saif AlSohad

---

因为您已经为bst设置了别名b，所以您必须使用b作为此表的名称。 - aRvi

Answer 1

编写此代码的最佳方式是限定 所有 列引用。因此，我建议:

SELECT b.N,
       (CASE WHEN b.P IS NULL
             THEN 'Root' 
             WHEN (SELECT COUNT(*) FROM BST b2 WHERE b2.P = b.N) > 0 
             THEN 'Inner'
             ELSE 'Leaf'
        END)
FROM bst b 
ORDER BY N;

这表明内部查询是一个相关子查询，它计算了BST中具有给定节点但不作为父节点的节点数量。

什么是条件？ 从逻辑上讲，这些条件是：

CASE WHEN <there is no parent>
     WHEN <at least one node has this node as a parent>
     ELSE <not a parent and no nodes have this as a parent>
END

请注意，我强烈反对在相关子查询中使用COUNT(*)来确定是否有任何匹配项。从性能和清晰度的角度来看，使用EXISTS要好得多：

SELECT b.N,
       (CASE WHEN b.P IS NULL
             THEN 'Root' 
             WHEN EXISTS (SELECT 1 FROM BST b2 WHERE b2.P = b.N) 
             THEN 'Inner'
             ELSE 'Leaf'
        END)
FROM bst b 
ORDER BY N;

- Gordon Linoff

---

b2是什么？我理解了b，因为你将表bst别名为b，那么b2是指什么？ - 01001010

子查询将其别名为b2。 - Gordon Linoff

Answer 2

在Hackerrank上，如果有帮助的话，你可以尝试以下内容：

select n,
case 
when p is null then 'Root'
when n in (select distinct(p) from bst) then 'Inner'
else 'Leaf'
end
from bst
order by n;

- Snehal Shukla

Answer 3

获取根节点P列的值为null。要获取内部列，P列的值将是不为null但可能出现多次的那些值，因此需要对列值进行去重，最后剩下的所有节点将是叶节点。

SELECT N, 
CASE 
   WHEN P IS NULL 
       THEN 'Root' 
   WHEN N IN (SELECT DISTINCT(P) FROM BST WHERE P IS NOT NULL) 
       THEN 'Inner' 
   ELSE 'Leaf' 
END 
FROM BST 
ORDER BY N;

- Aman Solanki

---

请在您的答案中添加一些解释，以便其他人可以从中学习。 - Nico Haase

获取根节点的P列值为空。要获取内部列，P列值将是不为空的那些，但它们可能会出现多次，因此需要对列值进行去重以获取这些列，最后剩下的所有节点都将是叶节点。 - Aman Solanki

请通过编辑您的答案添加所有解释。 - Nico Haase

Answer 4

SQL Oracle：

select n,(case when P is null then 'Root'
when N not in(select nvl(p,0) from bst) then 'Leaf'
else 'Inner' end) from bst order by n;

- Pranav Supsande

---

在DB2中工作过吗？你能给我解释一下nvl(p,0)的含义吗？ - 01001010

Answer 5

你在bst上有两个查询。一个主查询和一个带有COUNT的子查询。

子查询引用了自己的结果以及主查询(b.N)在它的WHERE部分中的结果。

通过删除b别名，您也删除了从子查询引用主查询的可能性。而p=bst.n等于p=n，因为bst是指子查询中的bst而不是主查询中的bst。

- t.niese

---

为什么我需要一个别名来引用子查询中的主查询？ - Saif AlSohad

@SaifAlSohad 因为两个查询都查询了 bst，所以 SELECT COUNT(*) FROM BST WHERE P = N 应该如何知道 P 是自己的查询，而 N 是主查询的，P 和 N 都是 bst 的列，因此在这种情况下，N 也将指向子查询的列。 - t.niese

Answer 6

1. 针对SQLServer

    select distinct parent.N as Node
          ,(case when parent.p is null then "Root"
                 when parent.n is not null and child.p is null then 'Leaf'
              ELSE 'Inner'
          end ) as Node_type
     from BST as parent
    left join bst as child
    on parent.n = child.p
    order by parent.n

- Aravind Addula

Answer 7

使用这个：

SELECT N,
case 
when P IS NULL then 'Root'
when N in (select N from BST where N in 
(select P from BST where P  IS NOT 
NULL)) then 'Inner'
else 'Leaf'
end
FROM BST order by N

- user22636985

---

虽然这段代码可能解决了问题，但是加上解释为什么以及如何解决问题的说明会大大提高你的帖子质量，可能会得到更多的赞同。记住你是在为未来的读者回答问题，而不仅仅是回答现在提问的人。 - undefined

Answer 8

SELECT BST.N,
CASE WHEN P IS NULL THEN 'Root'
WHEN BST.N in (SELECT DISTINCT BST.P FROM BST) THEN 'Inner'
ELSE 'Leaf'
END AS col_t
FROM BST
ORDER BY N;

- Fatima

---

请勿仅以代码作为答案发布，还应解释您的代码是如何解决问题的。带有解释的答案通常更有帮助和更高质量，并且更有可能获得点赞。 - Mark Rotteveel