从“能跑”到“能读”：Lc.450删除二叉搜索树中的节点代码重构记录-程序员充电站

最近在做 LeetCode 450（删除二叉搜索树中的节点）时，我写出了一版执行用时 0ms，击败 100% 用户的代码。从算法效率上讲，它是完美的：纯指针操作，没有递归开销，逻辑硬核。但从工程角度讲，它是十足的垃圾代码，可能下周我自己都看不明白我写的什么玩意了。

今天这篇博客，我想通过复盘这段代码，聊聊如何把代码从“能跑”进化到“能读”。

第一阶段：原始代码

我的核心思路非常直接：物理断开与重连。不搞递归那种值拷贝，直接找到节点，找到它的前驱（左子树最右节点），把前驱拎出来，物理替换掉目标节点。

这是我提交的原始版本（已通过所有测试用例）：

// 此代码虽然性能极致，但是问题一堆，写得一塌糊涂。 class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { // 【段落 1】 处理空节点的情况 if (!root) { return nullptr; } // 【段落 2】 处理key节点是根节点的情况 // 这里的逻辑：没有父节点，直接操作 root if (root->val == key) { if (!root->left && !root->right) { return nullptr; } else if (!root->left && root->right) { return root->right; } else if (root->left && !root->right) { return root->left; } else if (root->left && root->right) { //复杂的双子节点处理逻辑 TreeNode* old1 = root;// 【角色：被删节点】 (这里就是root本身) TreeNode* old2 = root;// 【角色：前驱节点的父节点】 (初始跟被删节点一样) root = root->left; while (root->right) {//潜在巨雷 root去当游标了 old2 = root; root = root->right; } if (old1 == old2) { //说明这个左节点就是左子树最右的节点了 root->right = old1->right; return root; } else if (old1 != old2) { old2->right = nullptr; root->right = old1->right; TreeNode* t = root; while (t->left) { t = t->left; } t->left = old1->left; return root; } } } // 【段落 3】 key节点不是根节点的情况 TreeNode* old0 = root; // 保存原始根 (最后要返回它) TreeNode* old1 = root; // 【角色：被删节点的父节点】 (上半部分没有，因为上半部分没父节点) TreeNode* old2 = root; // 【角色：被删节点 / 目标节点】 (初始是root，后面会变成目标) // 1. 先找到要删除的节点 while (root && root->val != key) {//潜在巨雷 root去当游标了 if (root->val > key) { old1 = root;// old1 紧跟 root ，充当父节点 root = root->left; } else { old1 = root;// old1 紧跟 root ，充当父节点 root = root->right; } } // 没找到直接返回 if (!root) { return old0; } // 到这里，root 指向的就是【要被删除的节点】 // 下面的逻辑开始处理删除 root (即 old2) 的操作 // 情况 1: 叶子节点 if (!root->left && !root->right) { if (old1->left == root) { old1->left = nullptr; return old0; } else { old1->right = nullptr; return old0; } } // 情况 2: 只有右孩子 else if (!root->left && root->right) { if (old1->left == root) { old1->left = root->right; return old0; } else { old1->right = root->right; return old0; } } // 情况 3: 只有左孩子 else if (root->left && !root->right) { if (old1->left == root) { old1->left = root->left; return old0; } else { old1->right = root->left; return old0; } } // 情况 4: 左右孩子都有 (最晕的地方来了) else if (root->left && root->right) { // 此时 root 是【要被删除的节点】 old2 = root;// 【角色：被删节点】 --> 对应上半部分的 old1 TreeNode* old3 = root;// 【角色：前驱节点的父节点】 --> 对应上半部分的 old2 // 开始寻找前驱 (左子树的最右节点) root = root->left; while (root->right) { old3 = root;// old3 紧跟，记录前驱的父亲 root = root->right; } // 循环结束后，root 变成了【前驱节点】(用来顶替被删节点的那个人) // 下面的逻辑和上半部分是完全镜像的，只是变量名下标+1了 // 特例：前驱节点的父节点 就是 被删节点本身 (即左子树没有右分支) if (old3 == old2) { if (old1->left == old2) { root->right = old2->right; old1->left = root; return old0; } else { root->right = old2->right; old1->right = root; return old0; } } // 通用情况：前驱节点在深处 // 此时：old1(爷爷), old2(被删), old3(前驱父), root(前驱) else if (old3 != old2) { old3->right = nullptr; root->right = old2->right; TreeNode* t = root; while (t->left) { t = t->left; } t->left = old2->left; if (old1->left == old2) { old1->left = root; return old0; } else { old1->right = root; return old0; } return old0; } } return root; } };

第二阶段：局部分析

这代码就是我一边想一边写的产物，脑子里在想各种情况如何处理，然后就实时写出各分支，游标、变量都是随时需要随时定义随时使用。等写完我自己再复盘的时候都没绷住，虽然能通过，但是实在是太有槽点了，以至于我必须新开一篇blog记录一下，我到底是怎么写出这种代码，以及该如何改进的。

我们一行行来分析问题出在哪：

1. 变量命名陷阱

TreeNode* old0 = root; TreeNode* old1 = root; TreeNode* old2 = root; TreeNode* old3 = root; // 在某些分支里还有 old3

问题：old家族大团结，我的小巧思。但old是什么意思？旧的？老的？old0到old3之间是什么关系？

这种命名迫使阅读者必须在脑子里维护一张映射表（old1=父亲, old2=目标…）。一旦代码逻辑变复杂，这张表瞬间就会崩塌。代码失去了自解释能力。

更要命的是，上下两部分的old1、old2甚至代表的含义都不一样。

2. 逻辑分裂

if (root->val == key) { ... } // 处理 Root // ... while (root && root->val != key) { ... } // 处理非 Root

问题：上半部分和下半部分的删除逻辑（叶子、单边、双边）是完全一样的！

仅仅因为根节点没有父节点，我就把代码复制了一遍。这导致任何一次逻辑修正（比如修复 BST 断链 bug）都需要改两个地方，漏改一处就是事故。

3. 指针复用混乱

while (root && root->val != key) { root = root->left; // root 变成了游标 } return old0; // 最后不得不返回保存的 old0

问题：root指针在函数里身兼数职：它是树的入口，是遍历的游标，又是某些分支的返回值。
这种“一鱼多吃”的做法极大地增加了认知负荷。输入参数应尽量保持只读或语义稳定。

4. 控制流层层递进

代码缩进呈现可怕的>>>>箭头状。

问题：if套if，else连else。
这种深层嵌套掩盖了主要逻辑流。

第三阶段：架构调整

在开始改代码之前，我们需要先在脑海里重构模型。

如何消除 Root 和非 Root 的区别？如何让逻辑变清晰？答案是：逻辑分层。

原始代码是“边找边删”，重构代码应该是流水线作业：

Search（定位）：统一找到目标节点target和它的父节点parent。
Decide（决策）：决定谁来接班（replacement）。
Link（缝合）：统一执行指针连接操作。

核心：在算法眼里，Root 只是一个parent为nullptr的普通节点。引入parent变量，且专门处理一下parent为nullptr时的情况，两套逻辑瞬间就能合并为一套。

第四阶段：重构

基于上述分析，保留我核心的“物理断开前驱”的高效逻辑，重构后的代码如下。

请对比阅读：

class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { // 1. 处理空树，减少一层嵌套 if (!root) return nullptr; // 2. 统一查找逻辑 // 使用语义化变量：target (目标), parent (父亲) TreeNode* target = root; TreeNode* parent = nullptr; while (target && target->val != key) { parent = target; // 父节点紧跟其后 if (key < target->val) { target = target->left; } else { target = target->right; } } // 没找到？直接返回 if (!target) return root; // 3. 决定谁来接班 (replacement) TreeNode* replacement = nullptr; // 情况 A: 左右双全 (最复杂的逻辑，保留原版的高效思路) if (target->left && target->right) { // 语义化变量：predecessor (前驱), predParent (前驱的父亲) TreeNode* predecessor = target->left; TreeNode* predParent = target; // 寻找左子树的最右节点 while (predecessor->right) { predParent = predecessor; predecessor = predecessor->right; } // 处理前驱的“身后事” if (predParent != target) { predParent->right = predecessor->left; // 爷爷接管孙子的左孩子 predecessor->left = target->left; // 前驱接管目标的左臂膀 } // 前驱接管目标的右臂膀 predecessor->right = target->right; // 选定接班人 replacement = predecessor; } // 情况 B: 只有左孩子 else if (target->left) { replacement = target->left; } // 情况 C: 只有右孩子 else if (target->right) { replacement = target->right; } // 情况 D: 叶子节点 (replacement 保持为 nullptr) else { replacement = nullptr;//这一块可以不写，写也只是为了清晰一点。 } // 4. 【缝合阶段】统一执行连接 // 这一步彻底消除了 Root 和 非 Root 的代码重复 if (!parent) { // 如果没有父亲，说明删的是 Root，直接换头 root = replacement; } else { // 如果有父亲，让父亲指向新的接班人 if (parent->left == target) { parent->left = replacement; } else { parent->right = replacement; } } // 此时整棵树的结构已完整，统一返回 return root; } };