視頻講解：https://www.bilibili.com/video/BV1tP41177us/?share_source=copy_web&vd_source=a935eaede74a204ec74fd041b917810c
文檔講解：https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E6%80%9D%E8%B7%AF
力扣題目：https://leetcode.cn/problems/delete-node-in-a-bst/
這道題主要是要分清楚刪除的節點有幾種情況
- 找不到刪除的點
- 找到了節點，左空右空，即刪除的是葉子節點，這種最簡單直接刪除就好了
- 左不空右空，直接將父節點跳過連到左子樹就行
- 左空又不空，同上鐮刀右子樹
- 左不空又不空，這種是最難的，根據二叉搜索樹的特性我們可以將目標節點的左子樹全部移到右子樹的最左葉子節點。
這就是這道題的整體思路。
仍需要注意的是節點的釋放，需要保存節點，在刪除root節點，否則會出現對空指針的操作。
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {//終止條件//1.沒找到刪除節點if(root == NULL) return NULL;//2.找到了if(root->val == key){ //刪除的是葉子節點if(root->left == NULL && root->right == NULL){delete root;return NULL;}//3.左不空右空else if(root->left != NULL && root->right == NULL ){auto retNode = root->left;delete root;return retNode;}//4.左空右不空else if( root->left == NULL&& root->right != NULL){auto retNode = root->right;delete root;return retNode;}//5.左不空又不空，把節點的左子樹放在右子樹的左葉子節點后else{TreeNode *cur = root->right;while(cur->left!=NULL){cur = cur->left;}//把左子樹放在右子樹的左葉子節點后cur->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp;//不要左子樹，直接返回右子樹return root;}}//單層遞歸if(key < root->val) root->left = deleteNode(root->left, key);if(key > root->val) root->right = deleteNode(root->right, key);return root;}
};
)
