[LeetCode] 450. Delete Node in a BST

1. 문제링크

https://leetcode.com/problems/delete-node-in-a-bst

Delete Node in a BST - LeetCode

 

2. key point

- Recursive로 문제를 해결할 수 있다

만약 key와 일치하는 node를 발견한 경우, 삭제할 위치에 올 node의 val을 왼쪽 오른쪽 subtree에서 찾아야한다.

만약 왼쪽 subtree에서 찾는 경우, 왼쪽 subtree의 가장 오른쪽에 있는 node가 가장 큰 값이 되기 때문에

왼쪽 subtree의 가장 높은 값으로 현재 root->val를 업데이트 해준다.

(오른쪽 subtree에서 찾는 경우 subtree의 가장 왼쪽에 있는 노드를 찾아서 root->val로 변경해줘야 함..! ㅇㅋ)

그리고 왼쪽 node는 재귀호출한다. 이 때 인자로 들어갈 key값을 위에서 변경해 준 root->val로 변경하는게 포인트!

 

 

3. solution

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return root;
        if(root->val == key){
            if(!root->left && !root->right)
                return NULL;
            if(!root->left || !root->right)
                return root->left ? root->left : root->right;

            TreeNode* temp = root->left;
            while(temp->right)
                temp = temp->right;            
            root->val = temp->val;
            root->left = deleteNode(root->left, temp->val);
        } else {
            if(root->val > key)
                root->left = deleteNode(root->left, key);
            else
                root->right = deleteNode(root->right, key);
        }
        return root;
    }
};