LeetCoding Challenge Oct.6: Insert Into a Binary Search Tree

LeetCode October Challenge の 6 日目。

今日の問題は Insert Into a Binary Search Tree。

問題の概要

• 数値をそのノードで保持している二分探索木 (Binary Search Tree) に新たな数値を追加する
  • 追加しようとしている数値と同じ値は二分探索木上に存在していないことが保証されている

考え方

• 大学の「アルゴリズムとデータ構造」的な講義の演習で遭遇しそうな問題ですね 🙄
  • C 言語が主流の時代ならまだしも、言語標準のランタイムライブラリが充実している現代において二分探索木の自前実装を迫られることが果たしてどれだけありうるのが甚だ疑問に感じる程度に、この手の問題はお仕事の役には立たないんじゃないかと思われる…
• それはさておき、ナイーブにやるなら普通に探索 → 進むべき先の子ノードが存在しないノードに遭遇したところで探索を終え、新たに生成したノード (TreeNode オブジェクト) をその子ノードとして挿入すればいいっしょ
• そういうわけでサクッと実装して難なく accept 🤗
  • Runtime 0ms だけど、分布のチャートを描けない程度にみんな 0ms でフィニッシュしているっぽい

コード

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        insertRecursive(root, val);
        return root;
    }

    void insertRecursive(TreeNode node, int val) {
        if (val < node.val) {
            if (node.left != null) {
                insertRecursive(node.left, val);
            } else {
                node.left = new TreeNode(val);
            }
        } else {  // val > node.val
            if (node.right != null) {
                insertRecursive(node.right, val);
            } else {
                node.right = new TreeNode(val);
            }
        }
    }
}