1. 先搞清楚题目到底在问什么1.1 二叉搜索树的基本性质在动手写删除逻辑之前得先把二叉搜索树的定义刻在脑子里。BSTBinary Search Tree不是随便一棵二叉树它有一个铁律任意节点的左子树中的所有节点值都小于当前节点值右子树中的所有节点值都大于当前节点值。这个性质不光是定义好看它决定了我们查找、插入、删除的每一步都能利用“比较大小”来缩小范围。很多人刷力扣的时候一上来就背删除节点的代码然后发现换个写法就不会了。问题的根源在于没有吃透BST的结构约束。比如删除一个节点不能像普通链表删除那样随手把指针一断就完事因为删完之后整棵树还得继续满足BST的定义。换句话说删除操作的目标是把目标节点拿掉同时保持剩下节点之间的相对大小关系不变让这棵树依然是合法BST。LeetCode对应这道题的编号是450题目名字就叫“Delete Node in a BST”。它属于力扣热题100和二叉树系列里的经典题也是面试中高频考察的二叉搜索树操作之一。很多刷题攻略里会把它排在二叉搜索树专题的中间位置前面一般是插入和查找后面才接验证BST、恢复BST这类进阶题。1.2 这题到底难在哪如果你已经会了BST的查找和插入会发现删除其实完全跨了一个难度档次。查找和插入的做法很简单小了往左走大了往右走走到空位就停下来干活。但删除不是“走一步看一步”这么简单难就难在删除一个节点之后你需要处理这个节点原来的位置以及它所有的后代节点。很多人初看这道题会想删叶子节点最简单直接让父节点对应的孩子指针指向null就行。这话没毛病但只对了四分之一。一个节点还有可能有左孩子、有右孩子或者左右孩子都有。每种情况处理方式都不一样尤其是“左右孩子都有”的情况是这道题的核心难点。我记得我第一次刷这道题的时候看完题第一反应是删掉节点之后把左子树接到右子树最左边的空位不就行了后来一画图发现不是这么回事而且实现起来代码特别绕。后来才明白真正优雅的做法是“找一个替身来顶替被删除节点的位置”而不是手动去拼接一堆子树。1.3 拿到题先别急着写代码我的习惯是拿到这种题先在纸上画一棵具体的树把删除各种位置的节点都画一遍把“删除前”和“删除后”的结构都画出来再开始写代码。这个方法对新手特别管用画完几种情况后代码的结构其实已经呼之欲出了。所以如果你还没开始画我先建议你画一根深度为3以上的树试着删除根节点、中间节点、叶子节点各一次感受一下差异。2. 删除节点的核心思路与四种情况2.1 情况一删除叶子节点叶子节点就是指没有左孩子也没有右孩子的节点。这种节点最“干净”删掉它不需要处理任何后代只需要让它的父节点指向它的那个指针变成null就行。递归实现的时候这个逻辑对应的是当递归结果返回null给上一层上一层重新接上这个返回值就完成了删除。这也是递归解题的一个常见套路——每个递归函数不直接修改父节点而是返回值给父节点由父节点更新孩子指针。画个具体例子说明树是 [5,3,6,2,4,null,7]要删除节点4。4是叶子节点它的父节点是3删除后3的右指针从指向4变成null就行。整棵树变成 [5,3,6,2,null,null,7]仍然是合法BST。2.2 情况二和情况三目标节点只有一个孩子这是第二种情况要删除的节点只有一个左孩子或者只有一个右孩子。处理方式也很直白让这个唯一的孩子顶替被删节点的位置。相当于父节点原本指向被删节点的那根指针改为指向被删节点的孩子。举例说明更方便理解。树是 [5,3,6,2,null,null,7]删掉节点33只有一个左孩子2那么删除后节点5的左指针直接指向2。树变成 [5,2,6,null,null,null,7]。如果被删节点只有一个右孩子逻辑一模一样只是把右孩子提上来。这里有一个新手很容易犯迷糊的点被删节点只有一个孩子的时候为什么可以直接让这个孩子顶上来因为被删节点的左子树或右子树整体是独立的BST子树其中所有节点本来就与被删节点的父节点保持合法的大小关系。比如上面例子里2是3的左孩子而3是5的左孩子所以2一定小于5把2直接接给5做左孩子完全合法。2.3 情况四有两个孩子用后继节点顶替这是最难的一种情况。当被删节点既有左孩子又有右孩子时无论让左孩子顶上来还是右孩子顶上来都会破坏BST的性质。比如被删节点5左子树里的最大值4右子树里的最小值6。如果让左孩子3直接顶上来那原来5的右子树全是大于5的节点就全挂到了3下面会违反“右子树所有节点大于根节点”的规则。反过来也一样。标准解法是在右子树里找到中序遍历下的第一个节点也就是右子树中最小的那个节点我们叫它“后继节点”把这个后继节点的值赋给被删节点然后再去右子树里递归删除这个后继节点。因为后继节点是右子树中的最小值它要么是叶子节点要么只有一个右孩子不会出现“两边都有孩子”的复杂局面所以递归删除它的时候只会命中前面已经处理过的简单情况。2.4 为什么用前驱或后继而不是其他节点有朋友会问为什么非要用中序遍历的后继节点随便找一个节点来顶替不行吗当然不行。删除两个孩子的节点替身必须满足一个条件替身的值要大于左子树里所有节点同时小于右子树里所有节点。整个树里能同时满足这两个条件的只有两种左子树的最大值前驱或者右子树的最小值后继。比如树是根节点10左子树最大节点8右子树最小节点11。删掉10要么把8放上来要么把11放上来。只有这两个位置的值与10的左右子树的大小关系是兼容的。顺便提示一下很多代码实现里用“后继”而不是“前驱”只是因为找到后继节点的写法更顺手。实际上用前驱也完全可以力扣测试用例不会因为替换方式不同而判错只要最终树是合法BST即可。3. 手写代码递归版与迭代版3.1 递归版实现递归版是这道题最推荐的写法理解成本低代码也短。核心思路是比较目标key和当前节点值决定往左走还是往右走把递归结果接回当前节点的孩子指针。找到目标节点后分四种情况处理。给出Python版本参考代码class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def deleteNode(self, root, key): if not root: return None if key root.val: root.left self.deleteNode(root.left, key) elif key root.val: root.right self.deleteNode(root.right, key) else: # 找到了要被删除的节点 if not root.left: return root.right if not root.right: return root.left # 左右孩子都在找后继节点 min_node self.findMin(root.right) root.val min_node.val root.right self.deleteNode(root.right, min_node.val) return root def findMin(self, node): while node.left: node node.left return node这段代码有几个细节值得展开说说。第一个细节是if not root.left: return root.right这一步实际上同时处理了“左为空右也为空”和“左为空右不为空”两个小情况。如果左右都为空返回的是None父节点接上None就等于删除了叶子节点。如果右不为空返回右孩子右孩子就能顶替上来。第二个细节是找后继节点那里把后继节点值赋给root然后在root.right分支里递归删除后继节点。为什么这里不像前面一样切成root.right self.deleteNode(root.right, min_node.val)之后直接结束因为把后继节点的值搬过来之后右子树里会出现两个相同值的节点必须删掉原来那个。递归删除后返回的右子树根节点要重新接回root的右指针。3.2 迭代版实现递归版虽然好写但面试里有时候会被要求写迭代版。迭代版的难点在于“如何记录目标节点的父节点”以及“找到目标节点后如何把新的子树接回去”。一个常见的迭代思路是用cur指针遍历树用parent记录cur的父节点。找到目标节点后根据目标节点的孩子情况构造一个subtree作为替换目标节点的子树。根据目标节点是parent的左孩子还是右孩子把parent对应的指针指向新subtree如果parent为空说明删除的是根节点直接返回新subtree。class Solution: def deleteNode(self, root, key): if not root: return None parent None cur root # 第一步找到目标节点 while cur and cur.val ! key: parent cur if key cur.val: cur cur.left else: cur cur.right # 没找到 if not cur: return root # 第二步根据目标节点的孩子情况构造替换子树 if not cur.left: new_subtree cur.right elif not cur.right: new_subtree cur.left else: # 左右都有取右子树最小节点当新根 new_subtree self.helper(cur) # cur的左右孩子都要挂到new_subtree上 new_subtree.left cur.left new_subtree.right cur.right # 第三步接回去 if not parent: return new_subtree elif parent.left cur: parent.left new_subtree else: parent.right new_subtree return root def helper(self, node): # 找到node右子树的最小节点并把它从原位置删除 parent node cur node.right while cur.left: parent cur cur cur.left if parent ! node: parent.left cur.right cur.right node.right return cur这段代码里最精巧的地方在helper函数。它做的事情是找到右子树的最小节点把它的父节点指向它的右孩子因为最小节点没有左孩子然后把自己return上去。如果最小节点本身就是右子树的根就不需要修改parent.left直接把这个节点提出来。迭代版代码比递归版长不少面试现场如果追求稳妥我仍然建议优先写递归版然后跟面试官提一句“迭代版我也能写”再展示代码。3.3 时间复杂度和空间复杂度对比这道题的时间复杂度是O(H)H是树高。对于普通树H是logN的量级但如果树退化成链表形状最坏是O(N)。力扣的测试用例一般不会特意构造退化树但刷题时要能意识到这个风险。空间复杂度递归版是O(H)因为递归栈的深度等于树高迭代版是O(1)没有使用额外空间。这也是面试中追问“能不能把空间复杂度降到O(1)”时迭代版的优势所在。4. 易错点排查与调试技巧4.1 常见错误清单第一类错误是忘记把递归结果接回父节点。有人会把root.left self.deleteNode(root.left, key)写成self.deleteNode(root.left, key)然后发现树根本没变化。这是因为节点之间靠指针连接如果你不更新左指针就算递归函数在里面把左子树删干净了父节点依然指向原来的那棵子树。第二类错误是左右孩子都存在时接错子树。有人会直接赋值root root.right或者root root.left这样做会丢掉另一棵子树里所有的节点。比如删除根节点左右子树都有直接换成右子树左子树就全丢了。第三类错误是删除两个孩子的节点后用后继值覆盖但忘记删除右子树里原来的后继节点。这种情况会导致整棵树里出现两个相同的值虽然不是语法错误但违反了BST节点的唯一性约束。第四类错误是对空树处理不当。如果根节点为空或者整棵树里找不到key应该直接返回原树。有的代码在递归到底没找到节点时返回一个新节点而不是None会导致树里凭空多出一个节点。4.2 实际调试过程中的经验刷这道题的时候建议用一种很“笨”但有效的调试方法打印中序遍历结果。因为合法BST的中序遍历结果一定是一个严格递增的序列如果你删除节点后中序遍历不是递增的说明结构已经被破坏了。这个方法对任何BST操作题都通用。比如你可以写一个辅助函数def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right)删除前后各打印一次对比结果。正常情况应该是原序列去掉目标值且仍然是递增的。另外一个小技巧是用力扣的“测试用例”参数化功能把边界情况的测试用例都过一遍。比如删除根节点、删除叶子节点、删除只有左孩子的节点、删除只有右孩子的节点、删除不存在的节点、在空树里删除。这六个用例跑通代码基本就稳了。4.3 面试里关于这道题的高频追问面试官通常不会只考“默写代码”还会顺着你的思路往下追问。比如“为什么两个孩子的节点要找后继或者前驱能不能用其它方式”这个问题对应的答案就是2.4节讲的替代节点合法性。“如果要删除的是一个很深的节点递归会不会栈溢出”这要求你分析递归深度并考虑迭代写法。“如果这棵树非常大有上亿个节点你的实现有没有问题”这时候需要提到磁盘存储、内存换页、分层遍历等实际工程问题至少能说出“递归深度受限于树高迭代能常数级空间”这一层。面试前建议把这些问题提前想清楚别等被问住了再现场编。5. 从一道题延伸到一类题5.1 二叉搜索树系列题型串联刷完删除节点这道题最好趁热把BST相关的题目一起串一下你会发现彼此之间关联度很高。查找节点是删除的基础因为删除的第一步就是查找插入节点和删除节点是互逆操作一个是在树里加叶子位置一个是把节点从摘下来再重新接好。我整理了一个刷题顺序供参考力扣700BST搜索→ 力扣701BST插入→ 力扣450BST删除→ 力扣98验证BST→ 力扣230BST中第K小的元素→ 力扣538 / 1038BST转累加树。这个顺序是一个由简单到复杂的过程每一步都建立在前一步的基础上。做完这一串你对BST的理解会比只刷一道题深刻得多。5.2 代码之外的几个建议2013年我开始刷力扣的时候也是从二叉树系列入门的。二叉树题目有一个共同特点递归结构非常清晰只要能定义清楚“当前层做什么、返回值给谁”代码基本就能写对。删除BST节点这道题我的个人体会是它不只是一个“背模板”的题目它更像是在考察结构约束意识。代码写得快不快是次要的关键是要能在心里把树的结构变化模拟出来。我在实际写代码时每一步都习惯问自己一个问题当前这棵树还是不是合法BST如果答案是肯定的再继续往下。最后再分享一个练习技巧看完本章内容后不要直接抄代码先把题目关掉在纸上画出删除各种节点的情况再用自己的话把每种情况的处理逻辑写出来最后一步才是写代码。这三步走完你大概率能自己写出完整实现。如果哪里卡住了再回头看看这篇博文的对应部分。