HackerRank 解鎖 - Binary Tree Nodes

當我們需要處理層級結構的資料時，HackerRank - Binary Search Tree Nodes 這題應該算是個很經典的 SQL 分類題。這篇就來拆解這道題目，從題目概述、輸入格式、輸出格式到 SQL 解法，一步步分析如何解決這道題目。(本篇以MS SQL Server語法教學)

題目概述

1. Root (根節點)：樹的起點，沒有父節點 (P IS NULL)。
2. Leaf (葉節點)：沒有子節點，也就是該節點的 N 不會出現在 P 欄位中。
3. Inner (內部節點)：既不是根節點，也不是葉節點，即它既有父節點，也有子節點。

我們的任務是根據 BST 資料表，判斷每個節點的類別，並按照 N 由小到大的順序輸出。

Input 格式

BST 表的結構如下：

• N：表示節點的值。
• P：表示節點的父節點值，若為 NULL，則表示該節點是根節點 (Root)。
• 節點值 (N) 唯一，不會重複。

Output 格式

我們希望查詢的結果如下：

• 依數字大小排序Node
• 判斷每個Node的類別

SQL 解法

首先觀察輸出類別判定的特性，我們會發現:

• Root (根節點)：當 P IS NULL 時，該節點是根節點。
• Leaf (葉節點)：當 N 不在 P 欄位中，代表該節點沒有子節點，則為葉節點。
• Inner (內部節點)：若 N 既有父節點 (P IS NOT NULL)，又出現在 P 欄位中，則是內部節點。

我們可以透過SQL裡的Case when 語法判定

• 找出 Root (根節點) → P IS NULL
• 找出 Leaf (葉節點) → N NOT IN (SELECT P FROM BST WHERE P IS NOT NULL)
• 剩下的就是 Inner (內部節點)

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

謝謝您花時間將此篇文章讀完，若覺得對您有幫助可以幫忙按個讚、分享來或是珍藏喔!也歡迎Follow我的Threads/ FB，持續追蹤生產力工具、商業分析、商業英文的實用範例，提升自己的職場力喔!