การลบโหนดใน BST (Delete Node in a BST) ใน C++

การลบโหนดใน Binary Search Tree (Delete Node in a BST)

ให้ BST และคีย์ k ต้องการลบโหนดที่มีค่า k แล้วคืน BST ที่อัปเดตแล้ว

ตัวอย่าง: ต้นไม้ [5,3,6,2,4,null,7] ลบ 3 → ผลลัพธ์ [5,4,6,2,null,7]

ขั้นตอนการแก้ปัญหา

1. ฟังก์ชัน deleteRoot(root) ลบโหนดราก:
   • ถ้าไม่มีลูกขวา คืนค่า left
   • หา inorder successor (ค่าน้อยที่สุดใน subtree ขวา)
   • ต่อ left ของ root ไปที่ left ของ successor
   • คืนค่า right ของ root
2. ฟังก์ชัน deleteNode(root, key):
   • ถ้า root == null || root.val == key คืนค่า deleteRoot(root)
   • เดินหาตำแหน่งของ key (ซ้ายถ้า key < val, ขวาถ้า key > val)
   • เมื่อเจอ เรียก deleteRoot บน child ที่ตรงกับ key

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    TreeNode* deleteRoot(TreeNode* root) {
        if (!root) return NULL;
        if (!root->right) return root->left;
        TreeNode* x = root->right;
        while (x->left) x = x->left;
        x->left = root->left;
        return root->right;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root || root->val == key) return deleteRoot(root);
        TreeNode* curr = root;
        while (true) {
            if (key < curr->val) {
                if (!curr->left || curr->left->val == key) {
                    curr->left = deleteRoot(curr->left);
                    break;
                }
                curr = curr->left;
            } else {
                if (!curr->right || curr->right->val == key) {
                    curr->right = deleteRoot(curr->right);
                    break;
                }
                curr = curr->right;
            }
        }
        return root;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [5,3,6,2,4,null,7] 3

Output: [5, 4, 6, 2, null, 7]