###### tags: `Leetcode` `medium` `tree` `python` `c++`

# 450. Delete Node in a BST

## [題目連結:] https://leetcode.com/problems/delete-node-in-a-bst/description/

## 題目:
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the **root node reference** (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.

If the node is found, delete the node.


## 解題想法:
* 此題為給一Binary Search Tree，刪除特定node
* **需確保刪除後，仍維持BST**
* 想法:
* 對於欲刪除的node: root，用
(1) 其右子(root.right)中，找最小的左子取代root.val，並在遞迴刪除該最小的左子(避免重複)
(2) 其左子(root.left)中，找最大的右子取代root.val，並在遞迴刪除該最小的右子(避免重複)
* 以下code用(1)撰寫

* 流程:
* **Case1**:
* 若root空:
* return root
* **Case2**: if root.val > key
* 要遞迴往左子找
* root.left=deleteNode(root.left, key)
* **Case3**: if root.val < key
* 要遞迴往右子找
* root.right=deleteNode(root.right, key)
* **Case4**: if root.val==key:
* 找到刪除目標，要找對象取代
* case1: 若該目標沒有左子
* 直接回傳其右子作為取代即可

            if not root.left:
                return root.right

* case2: 若該目標沒有右子
* 直接回傳其左子作為取代即可

            if not root.right:
                return root.left

* case3: **若目標具有左右子**
* 找其右子最小的node替換掉要被刪掉的目標
* 再遞迴將該node刪掉 避免重複

            tmp=root.right
            while tmp.left:
                tmp=tmp.left
            root.val=tmp.val
            root.right=self.deleteNode(root.right,tmp.val)

* **Final**:
* return root

## Python:

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return root
        if root.val>key: #要往左子找
            root.left=self.deleteNode(root.left,key)
        elif root.val<key: #往右子找
            root.right=self.deleteNode(root.right,key)
        elif root.val==key: #找到ㄌ
            #case1: 若該目標沒有左子 
            if not root.left:
                #則直接回傳其右子做為取代就好
                return root.right
            #case2: 若該目標沒有右子
            if not root.right:
                return root.left
            #case3: 若該目標具有左右子 
            #找其右子最小的node替換掉要被刪掉的目標
            #再遞迴將該node刪掉 避免重複
            tmp=root.right
            while tmp.left:
                tmp=tmp.left
            root.val=tmp.val
            root.right=self.deleteNode(root.right,tmp.val)
        return root
    
root=TreeNode(5)
root.insertLeft(3)
root.insertRight(6)
root.left.insertLeft(2)
root.left.insertRight(4)
root.right.insertRight(7)
print("Input:",end='')
root.printTree()

result=Solution()
ans=result.deleteNode(root,3)
print("Output:",end='')
root.printTree()

## C++:

/**
 * 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:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root)
            return nullptr;
        else if (root->val < key)
            root->right=deleteNode(root->right, key);
        else if (root->val > key)
            root->left=deleteNode(root->left, key);
        else if (root->val==key){
            if (!root->left)
                return root->right;
            else if (!root->right)
                return root->left;
            else{
                TreeNode *tmp=root->right;
                while (tmp->left){
                    tmp=tmp->left;
                }
                root->val=tmp->val;
                root->right=deleteNode(root->right, tmp->val);
            }
        }
        return root;
    }
};