如何从450删除特定节点于二叉搜索树？

本文共计653个文字，预计阅读时间需要3分钟。

创意思考：删除一个节点的时刻，可能遇到以下情况：找不到节点，那么就返回最初的最优树；找到了叶子节点，直接接在节点上即可；节点一边是空的，另一边是“+。

✅做题思路or感想：

在删除一个节点的时候可能有以下情况

• 找不到节点，那么就之间返回最开始的树就好了
• 找到了节点
  • 节点是叶子节点，则直接删掉就好了
  • 节点一边是空的，另一遍是有子树的，则直接把该节点的子节点返回给该节点的前一个节点，然后把这个节点删除
  • 节点两边都是非空的，则把节点的左子树接到右子树的最左面（因为左子树的数值一定全部小于右子树的数值，而右子树的最小值就是右子树最左面的值，所以要把左子树接到右子树的最左面！)

class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { //没找到节点，则直接返回原树 if (root == nullptr)return root; //找到了节点 if (root->val == key) { //节点是叶子节点 if (!root->left && !root->right) { delete root; return nullptr; //节点只有一边是空的 } else if (!root->left && root->right) { TreeNode* temp = root->right; delete root; return temp; } else if (root->left && !root->right) { TreeNode* temp = root->left; delete root; return temp; //节点两边非空 } else { //这里要注意，因为要找的是右子树最左面，所以要用一个循环来找右子树最左面！！！！ TreeNode* cur = root->right; while (cur->left != nullptr) { cur = cur->left; } cur->left = root->left; TreeNode* temp = root->right; delete root; return temp; } } //其实上面都算得上是递归终止条件的部分，下面是我个人最不会的部分：递归单层逻辑 //这里主要是利用二叉搜索树来找哪一个子树要修改（即删除子节点） //删除操作其实是一种父子节点间赋值的操作！！！这种要上下联动的操作用有 //返回值的递归函数来解比较方便，如果用没有返回值的递归来解，则要多一个 //pre节点来记录上一个节点，比较麻烦! if (root->val > key)root->left = deleteNode(root->left, key); if (root->val < key)root->right = deleteNode(root->right, key); return root; } };