删除二叉搜索树中的节点涉及结构调整！删除二叉搜索树中的节点题目链接：https://leetcode-cn.com/problems/delete-node-in-a-bst/确定二叉搜索树的根节点root和一个valuekey，删除二叉查找树中key对应的节点，保证二叉查找树的性质不变。返回对二叉搜索树的（可能更新的）根节点的引用。一般来说，删除一个节点可以分为两步：首先找到需要删除的节点；如果找到，请将其删除。说明：要求算法的时间复杂度为O(h)，h为树的高度。示例：想法搜索树中删除节点比添加节点要复杂得多。有很多情况需要考虑，所以要做好准备。递归递归三部曲：确定递归函数参数和返回值说到递归函数的返回值，在二叉树中：搜索树中的插入操作，通过递归返回值添加新的节点，节点也可以是通过递归返回值删除。代码如下：TreeNode*deleteNode(TreeNode*root,intkey)确认终止条件遇到null返回。其实这也意味着没有找到被删除的节点，if(root==nullptr)returnroot遍历到空节点后直接返回；这里的递归逻辑是为了理清平衡二叉树删除节点时遇到的所有情况。有以下五种情况：第一种情况：没有找到删除节点，遍历空节点，直接找到删除节点第二种情况：左右孩子为空（叶子节点），删除节点根节点的第三种情况：被删除节点的左孩子为空，右孩子不为空，删除节点，填充右孩子，返回右孩子为第四种情况：被删除节点的右孩子为空，左孩子不为空，则删除该节点，填充左孩子，返回左孩子作为根节点。第5种情况：左右子节点都不为空，则将被删除节点的左子树头节点（左孩子）放入被删除节点的右子树最左节点的左孩子上，返回右被删除节点的子节点作为新的根节点。第5种情况有点难理解，看下面这个动画：删除二叉查找树动画中的节点在二叉查找树中，删除元素7，然后删除该节点（元素7）的左孩子为5，删除该节点（元素7的右子树的最左边节点）为元素8。将被删除节点（元素7）的左孩子放在被删除节点（元素7）右子树的最左边节点（元素8）的左孩子上，即向左移动根节点为5的子树8位置的孩子。要删除的节点（元素7）的右子节点（元素9）是新的根节点。.这样就完成了删除元素7的逻辑。最好手工画一个图，尽量删除一个节点。代码如下：if(root->val==key){//第二种情况：左右孩子为空（叶子节点），直接删除该节点，返回NULL为根节点//第三种情况：它的左孩子为空，右孩子不为空，删除节点，填充右孩子，返回右孩子作为根节点if(root->left==nullptr)returnroot->right;//第四种情况：右孩子为空，左孩子不为空，删除节点，填充左孩子，返回左孩子为根节点elseif(root->right==nullptr)returnroot->left;//第五种情况：左右子节点都不为空，将被删除节点的左子树放入被删除节点右子树的最左子节点的左孩子位置//并返回右孩子删除的节点作为新的根节点。else{TreeNode*cur=root->right;//找到右子树的最左边节点while(cur->left!=nullptr){cur=cur->left;}cur->left=root->left;//将要删除的节点（root）的左子树放在cur的左孩子的位置TreeNode*tmp=root;//保存根节点，删除root=root->right;//返回theoldroot节点的右孩子作为新的rootdeletetmp;//释放节点内存（这里不写也没关系，但是C++最好手动释放）returnroot;}}这是相当于把新节点返回到上一层，而上一层需要使用root->left或者root->right来捕捉，代码如下：if(root->val>key)root->left=deleteNode(root->left,key);if(root->valright=deleteNode(root->right,key);返回根；整体代码如下：（注释中：案例1、2、3、4、5严格对应上面的分析）classSolution{public:TreeNode*deleteNode(TreeNode*root,intkey){if(root==nullptr)returnroot;//第一种情况：没有找到删除的节点，遍历空节点直接返回if(root->val==key){//第二种情况情况：左右孩子都是empty(叶子节点)，直接删除节点，返回NULL为根节点//第三种情况：左孩子为空，右孩子不为空，删除节点，填充右孩子，返回右孩子是根节点if(root->left==nullptr)returnroot->right;//第四种情况：右孩子为空，左孩子不为空，删除节点，填充左孩子，返回左childasRootnodeelseif(root->right==nullptr)returnroot->left;//第5种情况：左右子节点都不为空，则将删除节点的左子树放到右子树的末尾of被删除的节点左节点的左孩子的位置//并返回被删除节点的右孩子作为新的根节点。else{TreeNode*cur=root->right;//找到右子树的最左边节点while(cur->left!=nullptr){cur=cur->left;}cur->left=root->left;//将要删除的节点（root）的左子树放在cur的左孩子的位置TreeNode*tmp=root;//保存根节点，删除root=root->right;//返回theoldrootTherightchildofthenewrootdeletetmp;//释放节点内存（这里可以不写，C++最好手动释放）returnroot;}}if(root->val>key)root->left=deleteNode(root->left,key);if(root->valright=deleteNode(root->right,key);returnroot;}};普通二叉树的删除方法这里我介绍的是一种通用的删除，普通二叉树的删除方法（没有使用搜索树的特性，遍历整棵树），通过交换值的操作来删除目标节点。代码中对目标节点（即要删除的节点）进行了两次操作：第一次是与目标节点右子树的最左节点进行交换。第二次直接被NULL覆盖。思路有点绕，有兴趣的同学可以自己画图理解。代码如下：（关键部分已经注释掉）classSolution{public:TreeNode*deleteNode(TreeNode*root,intkey){if(root==nullptr)returnroot;if(root->val==key){if(root->right==nullptr){//这里第二次操作的目标值：最后的删除函数returnroot->left;}TreeNode*cur=root->right;while(cur->left){cur=cur->left;}swap(root->val,cur->val);//这里第一次操作目标值：交换目标值右子树的最左边节点。}root->left=deleteNode(root->left,key);root->right=deleteNode(root->right,key);returnroot;}};这段代码比较短小精悍，但是我觉得不是很好，实用性不强，推荐第一种写法！迭代删除节点的方法还是比较复杂的，但是我已经在递归方法中介绍了它的本质。最重要的是删除节点的操作（动画模拟的过程）代码如下：目标节点的右子树//并返回目标节点的右子节点作为新的根节点//就是动画中的模拟过程TreeNode*deleteOneNode(TreeNode*target){if(target==nullptr)returntarget;if(target->right==nullptr)returntarget->left;TreeNode*cur=target->right;while(cur->left){cur=cur->left;}cur->left=target->left;returntarget->right;}public:TreeNode*deleteNode(TreeNode*root,intkey){if(root==nullptr)returnroot;TreeNode*cur=root;TreeNode*pre=nullptr;//记录cur的父节点删除curwhile(cur){if(cur->val==key)break;pre=cur;if(cur->val>key)cur=cur->left;elsecur=cur->right;}if(pre==nullptr){//如果搜索树只有头节点returndeleteOneNode(cur);}//pre要知道是否删除leftchild或右孩子if(pre->left&&pre->left->val==key){pre->left=deleteOneNode(cur);}if(pre->right&&pre->right->val==key){pre->right=deleteOneNode(cur);}returnroot;}};小结看完这篇文章，你会发现二叉搜索树中删除节点比添加节点更复杂，主要是因为二叉搜索树中添加节点只需要添加叶子，不涉及结构调整，删除节点的操作涉及结构调整。这里我们还是利用递归函数的返回值来完成从二叉树中移除节点的操作。这里最关键的逻辑是第五种情况（删除一个左右孩子都不为空的节点），这种情况一定要想清楚。而且即使想清楚了，对应的代码也未必能写出来，所以这道题不仅考思维逻辑，更考代码能力。在递归中，我给出了两种写法。推荐大家学习第一种方式（利用搜索树的特性），第二种方式递归写起来其实比较绕。最后我也给出了相应的迭代方法，就是模拟递归方法中删除节点的逻辑，但是需要一个prerecordcur的父节点，方便删除操作。迭代法其实不好写，所以如果你是初学者，完全掌握第一个递归的写法就够了。其他语言版本JavaclassSolution{publicTreeNodeleteNode(TreeNoderoot,intkey){root=delete(root,key);returnroot;}privateTreeNodelete(TreeNoderoot,intkey){if(root==null)returnnull;if(root.val>key){root.left=delete(root.left,key);}elseif(root.valTreeNode:ifnotroot:returnroot#第一种情况：没有找到被删除的节点，遍历到空节点直接返回ifroot.val==key:ifnotroot.leftandnotroot.right:#第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点delrootreturnNoneifnotroot.leftandroot.right:#第三种情况：左孩子为空，右孩子不为空，删除节点，填充右孩子，并返回右孩子作为根节点tmp=rootroot=root.rightdeltmpreturnrootifroot.leftandnotroot.right:#第四种情况：其右孩子为空，左孩子不为空，删除节点，补左child，返回左孩子作为根节点tmp=rootroot=root.leftdeltmpreturnrootelse:#第五种情况：左右孩子节点都不为空，则删除节点的左孩子树放在被删除节点的右子树的最左节点的左孩子位置v=root.rightwhilev.left:v=v.leftv.left=root.lefttmp=rootroot=root.rightdeltmpreturnrootifroot.val>键：根。left=self.deleteNode(root.left,key)#leftrecursiveifroot.val
