LeetCode450：删除二叉搜索树中的节点

本文主要是介绍LeetCode450：删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

在这里插入图片描述

代码

/*1.没找到删除的节点:返回节点2.叶子节点：直接删除3.左不空右空：直接使用左孩子替换4.左空右不空：直接使用右孩子替换5.左右都不空：将左孩子放到右孩子的最左侧的节点，然后将右孩子替换要删除的节点
*/
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;if (root->val == key) {//叶子节点if (root->left == nullptr && root->right == nullptr){delete root;return nullptr;}//左不空右空else if (root->right == nullptr) {TreeNode* retNode = root->left;delete root;return retNode;}//左空右不空else if (root->left == nullptr) {TreeNode* retNode = root->right;delete root;return retNode;}//左右都不空else if (root->left && root->right) {TreeNode* cur = root->right;while (cur->left) cur = cur->left;cur->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp;return root;}}else if (key < root->val) root->left = deleteNode(root->left, key);else if (key > root->val) root->right = deleteNode(root->right, key);return root;}
};