235. 二分探索木の最近共通先祖

二分探索木（BST）の根ノードと二つの指定ノードが与えられた場合、その二つのノードの最近共通先祖を返す関数を作成します。

struct TreeNode* findCommonAncestor(struct TreeNode* tree, struct TreeNode* n1, struct TreeNode* n2) {
    if (tree == NULL) {
        return NULL;
    }
    if (tree->val > n1->val && tree->val > n2->val) {
        struct TreeNode* left = findCommonAncestor(tree->left, n1, n2);
        return left != NULL ? left : NULL;
    }
    if (tree->val < n1->val && tree->val < n2->val) {
        struct TreeNode* right = findCommonAncestor(tree->right, n1, n2);
        return right != NULL ? right : NULL;
    }
    return tree;
}

このアルゴリズムは、BSTの性質を利用します。根ノードから下に向かって探索し、最初にn1とn2の値の範囲内に位置するノードが最近共通先祖となります。

701. 二分探索木へのノード挿入

指定された値をBSTに挿入し、挿入後のBSTのルートを返します。

struct TreeNode* insertIntoBST(struct TreeNode* root, int value) {
    if (root == NULL) {
        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        newNode->val = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (root->val > value) {
        root->left = insertIntoBST(root->left, value);
    } else {
        root->right = insertIntoBST(root->right, value);
    }
    return root;
}

ルートがNULLの場合、新規ノードを作成します。値が現在のノードの値よりも小さい場合は左部分木、大きい場合は右部分木に再帰的に挿入します。

450. 二分探索木からのノード削除

BSTから指定された値のノードを削除し、BSTの性質を維持します。

struct TreeNode* deleteNode(struct TreeNode* node, int deleteVal) {
    if (node == NULL) {
        return NULL;
    }
    if (node->val == deleteVal) {
        if (node->left == NULL && node->right == NULL) {
            return NULL;
        } else if (node->left != NULL && node->right == NULL) {
            return node->left;
        } else if (node->right != NULL && node->left == NULL) {
            return node->right;
        } else {
            struct TreeNode* successor = node->right;
            while (successor->left != NULL) {
                successor = successor->left;
            }
            successor->left = node->left;
            return node->right;
        }
    }
    if (node->val > deleteVal) {
        node->left = deleteNode(node->left, deleteVal);
    } else {
        node->right = deleteNode(node->right, deleteVal);
    }
    return node;
}

削除対象のノードが見つかった場合、以下の五つの状況を考慮します：

• 削除ノードが葉ノードである場合
• 削除ノードが左の子ノードのみを持つ場合
• 削除ノードが右の子ノードのみを持つ場合
• 削除ノードが両方の子ノードを持つ場合