###### tags: `LeetCode` `BST` `Recursion` `Medium`
# LeetCode #450 [Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/)
### (Medium)

給定一個二叉搜索樹的根節點 root 和一個值 key，刪除二叉搜索樹中的 key 對應的節點，並保證二叉搜索樹的性質不變。返回二叉搜索樹（有可能被更新）的根節點的引用。

一般來說，刪除節點可分為兩個步驟：

* 首先找到需要刪除的節點；
* 如果找到了，刪除它。

---
方法為將該節點在整個樹中的的右邊節點(中序遍歷時在該節點右邊的的節點, 右子樹中的最左節點)的值與目標值對換, 然後刪掉該節點(該節點必定為葉節點, 可以直接刪除)。(找最靠近目標節點的最左節點也可以)

而因為兩值交換後目標節點會變成最底層的葉節點. 因此還是要遞迴呼叫刪除節點, 直到找到位置在葉節點的該節點, 並將其改為nullptr。

---

/**
 * 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;
        if(root->val==key){
            if(!root->right)return root->left;
            TreeNode* node = root->right;
            while(node->left)node=node->left;
            swap(root->val, node->val);
            root->right=deleteNode(root->right, key);
            return root;
        }
        //下兩行目標為尋找該節點
        if(root->val<key)root->right = deleteNode(root->right, key);
        else if(root->val>key)root->left = deleteNode(root->left, key);
        
        return root;
    }
};