[ leetcode ] 450. Delete Node in a BST

Binary Search Tree가 주어졌을 때, 한 노드를 제거하고 재배치한 BST를 반환하는 문제입니다.

여러 경우의 수가 있지만, 우선 한 노드를 삭제할 때 기본적인 규칙은 다음과 같습니다.

1. 삭제할 노드의 자식 중 한쪽 노드만 존재하는 경우, 삭제할 노드 위치를 해당 노드로 변경
2. 삭제할 노드의 자식 둘 다 존재하는 경우, 왼쪽 자식 노드를 삭제할 노드로 대체한다고 하면 왼쪽 자식 노드의 오른쪽 노드를 
   삭제할 노드의 오른쪽 자식의 가장 왼쪽 자식에 추가해주는 로직이 필요 (반대의 경우도 가능)

아래 링크를 참고하면 이해에 도움이 될 것 같습니다.
https://leetcode.com/problems/delete-node-in-a-bst/solutions/1591176/c-simple-solution-w-images-detailed-explanation-iterative-recursive-approach/

✅ [C++] Simple Solution w/ Images & Detailed Explanation | Iterative & Recursive Approach - Delete Node in a BST - LeetCode

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void delete_current_node(TreeNode*& current, TreeNode*& parent) {
        if (current->left) {
            if (current->right) {
                TreeNode* temp = current->right;
                while (temp->left) temp = temp->left;
                temp->left = current->left->right;
                current->left->right = current->right;
            }
            if (parent->left == current) parent->left = current->left;
            else if (parent->right == current) parent->right = current->left;
            else parent = parent->left;
        }
        else if (current->right) {
            if (current->left) {
                TreeNode* temp = current->left;
                while (temp->right) temp = temp->right;
                temp->right = current->right->left;
                current->right->left = current->left;
            }
            if (parent->left == current) parent->left = current->right;
            else if (parent->right == current) parent->right = current->right;
            else parent = parent->right;
        }
        else {
            if (parent->left == current) parent->left = NULL;
            else if (parent->right == current) parent->right = NULL;
            else parent = NULL;
        }
    }

    pair<TreeNode*, TreeNode*> findNode(TreeNode* current, TreeNode* parent, int key) {
        if (!current) return make_pair(nullptr, nullptr);
        if (current->val > key) return findNode(current->left, current, key);
        else if (current->val < key) return findNode(current->right, current, key);
        else return make_pair(current, parent);
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return NULL;
        pair<TreeNode*, TreeNode*> delete_node;
        if (root->val > key) delete_node = findNode(root->left, root, key);
        else if (root->val < key) delete_node = findNode(root->right, root, key);
        else delete_current_node(root, root);
        
        if (delete_node.first != nullptr) delete_current_node(delete_node.first, delete_node.second);
        return root;
    }
};