企业官网建设流程全解析

算法复健到今天已经第16天了，Day16我做了一个BST专场：LeetCode 235、701、450三道题一口气刷完。先说感受：这三道题官方难度分别是Easy、Medium、Medium，但实际刷下来的体感完全不是这个排序——701反而是最顺手的，450则让我反复修改才彻底跑通。这篇复盘会把选题逻辑、每道题的思路和代码、以及那些“不踩一次根本学不会”的坑全部摊开，适合正在做算法复健、准备技术面试，或者单纯想把二叉树递归基本功打扎实的朋友。

很多人安排刷题计划时容易犯一个错误：按题号顺序硬刷。我复健前期也这么干过，结果是今天做链表、明天碰动态规划、后天又跳回二叉树，知识点完全没沉淀。后来我改成按主题集中刷：先花几天把二叉树遍历打底，再集中处理树属性类题目，到了第16天，我决定把BST的增、删、查三件套放在同一个session里一次打穿。下面就是完整的复盘过程。

1. Day16的选题逻辑：为什么把235、701、450绑在一起

1.1 BST到底是什么，凭什么能“指方向”

二叉搜索树（Binary Search Tree，BST）的定义其实很好记：对任意节点而言，左子树所有节点的值都小于它，右子树所有节点的值都大于它，并且左右子树本身也都是BST。刷题时通常会额外假设节点值唯一，这个假设一旦成立，整棵树就自带了一个极其强大的性质：中序遍历结果是严格升序序列。

我比较喜欢用“会指路的树”来理解BST。普通二叉树里你站在一个节点上，不知道目标在左边还是右边，只能两边都探索；但在BST里，你只需要拿着目标值和当前节点值比大小，答案要么在左、要么在右，二选一。这个“方向感”就是BST所有高效操作的根本来源。查找、插入、删除，全部能用一条查找路径完成，而不需要遍历整棵树。

1.2 三题的分工：增、删、查正好是一套连招

把235、701、450放在同一天刷，不是因为题号相邻，而是因为它们各自覆盖了BST操作里最核心的三件事：查、增、删。我刷完之后列过一个对比表，建议你也按这个视角去归类：

这三个操作在考试和面试里往往不单出，而是揉进更复杂的题里，比如“BST加一个自平衡逻辑”“BST实现迭代器”“序列化与反序列化”。如果查、增、删的基础版本都磕磕绊绊，后面这些组合题基本没法做。把它们绑在一起刷的最大好处是：每一道题理解的模式，都能在下一道题里复用。

1.3 关于刷题顺序的建议

如果完全按题目编号，235 → 701 → 450是一个“由易到难再变难”的过程，作为复健热身很合理。但如果让我给自己安排顺序，我会推荐先做701，再做235，最后啃450。

为什么？因为701是三道题里递归结构最典型的：通过插入操作把“递归返回值要被父节点接住”这个概念练熟，后面235你只需要把这个模式套进判断逻辑里，450则是在这个基础上再叠加“删除时子树如何重新连接”的复杂度。先热身、再深入、最后挑战最复杂的重连逻辑，体感上会顺畅很多。我这次因为想复盘原题顺序，是按235-701-450刷的，过程中明显能感觉到450那题在结构重建这一步才是真正的分水岭。

1.4 开始前必须具备的基线知识

如果你想跟着这份复盘自己动手做一遍，建议先确保具备四个基础：

• 会写二叉树的前序、中序、后序遍历，尤其是中序遍历；
• 理解递归三要素：终止条件、返回值、单层递归逻辑；
• 知道C++里二叉树节点的标准定义长什么样；
• 对空指针检查保持敏感：凡是访问cur->left、cur->right，先确认cur不为空。

标准节点定义参考：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

这个结构体在不同的题目里字段都一样，区别只在算法本身。接下来我按实际刷题顺序，把三道题逐一拆开讲。

2. LC 235 最近公共祖先：BST的有序性把LCA变成了区间判断题

2.1 先把题目翻译成人话

题目是给一棵BST，以及树中两个节点p、q，要求返回p和q的最近公共祖先。所谓最近公共祖先，就是同时出现在p和q祖先链上的最深的那个节点。用大白话说：p和q在树里往上走，最先相遇的那个节点就是答案。

普通二叉树做这道题时，你往往要从根开始递归左右两边，因为没有任何大小信息可以帮忙判断。但在BST里，每条路径都是沿着大小方向走的，所以问题的本质从“寻找两条路径的交点”简化成了“判断root的值落在哪个区间”。

2.2 核心判断：root夹在p和q之间就是终点

假设当前遍历节点是root，有三个情况需要判断：

• 如果root->val比p和q的值都大，说明p、q两个目标都在左子树里，LCA不可能在右子树，所以直接向左走；
• 如果root->val比p和q的值都小，说明两个目标都在右子树，直接向右走；
• 否则，root本身就是答案。

最后这一步是很多人不理解的地方。举个例子：p的值是2，q的值是8，当前root的值是5。这时候p在左子树，q在右子树，root就是p和q第一层相遇的分叉点。分叉点就是公共祖先，而且因为是一路向下找出来的，所以它一定是“最近”的那个。如果root的值刚好等于p或q，那root也是答案，因为一个节点可以自己作为自己的祖先。

2.3 递归实现：代码短，但每一行都要想清楚

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return NULL; if (root->val > p->val && root->val > q->val) { return lowestCommonAncestor(root->left, p, q); } if (root->val < p->val && root->val < q->val) { return lowestCommonAncestor(root->right, p, q); } return root; }

递归版的时间复杂度是O(h)，h是树的高度，空间复杂度也是O(h)，因为递归栈的深度就是搜索路径长度。这个代码看起来很短，但要注意两个细节：第一，题目保证了p和q都在树中，所以递归过程中不会出现跑到null的情况，root == NULL那个判断只是防御性的；第二，比较的时候必须用p和q的val同时比较，而不是写成root->val在p和q之间这种区间判断，因为p、q传给函数的顺序是不定的。

2.4 迭代实现：把递归栈换成while循环

既然每步都只有两个方向，递归改成迭代非常简单，而且空间能压到O(1)：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root) { if (root->val > p->val && root->val > q->val) { root = root->left; } else if (root->val < p->val && root->val < q->val) { root = root->right; } else { return root; } } return NULL; }

这个写法我在面试时更喜欢用，因为面试官问“能不能把空间复杂度降到O(1)”，你直接把递归改成while循环，思路又清晰又省空间。

2.5 一个关键对比：没有有序性时，普通二叉树LCA有多吃力

如果你做过普通二叉树的LCA，再回来做235，会明显感觉到BST的“减负”有多大。普通二叉树的递归长这样：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left && right) return root; return left ? left : right; }

因为没有大小信息，普通二叉树必须同时递归左右两侧，才能知道p和q分别出现在哪里。时间复杂度和节点总数n相关，最坏O(n)。而BST版本只走一条路径，最坏也是O(h)。这个对比很好地解释了“有序性剪枝”的价值：方向一旦确定，另一侧的搜索空间就直接被丢弃了。

2.6 这题需要注意的边界

根节点为空时直接返回空；p和q相同的情况也直接返回root；树里只有单边路径时，递归会一直沿着同一方向走到root成为答案为止。我自己曾经犯过一个错：把方向判断里的>写成了>=，在极端情况下会漏掉root本身等于某个目标值的情况，最后在测试样例里WA了一次。方向比较用严格大于、严格小于，是最稳妥的写法。

3. LC 701 插入操作：关键不是找位置，而是把新节点“接”回来

3.1 题意的隐藏信息：插入方式不止一种

题目给一个BST根节点和一个整数val，要求把新节点插入进去并返回根。如果你细想，BST插入的合法答案其实很多：你可以把新节点做成新的根，然后重组整棵树，这在BST性质上也是合法的。但为什么标准解法都选择从根开始一路找空位，把新节点挂到叶子位置？因为这种做法的代价最小、思路最直白，而且不需要动已有结构。

严格说这不是唯一的合法结构，但做题和工程实现都追求“最小改动”，所以选择叶子插入策略。

3.2 递归版：返回值就是父子之间的“粘合剂”

TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) { return new TreeNode(val); } if (val < root->val) { root->left = insertIntoBST(root->left, val); } else { root->right = insertIntoBST(root->right, val); } return root; }

这段代码我刷了无数遍，核心就一句话：函数返回的是“处理完之后的子树根”。当递归遇到null时，它创建一个新节点并返回，这个新节点被上一层赋给root->left或root->right；当递归遇到非空节点时，它更新左或右孩子的指针，然后把自己返回。这个“返回自己”很关键，因为对上层调用来说，这一整棵子树虽然内部结构变了，但对外仍然是一棵完整的子树，父节点只需要接住这棵子树的根就行。

3.3 为什么沿着方向一路走到空位，BST性质就不会坏

你可能会问：为什么不是插入完再重新验证一遍？实际上根本不需要。因为插入路径上的所有判断都遵循BST规则——val小就往左走，val大就往右走。新节点最终落到哪棵空子树里，它和沿途所有节点的相对大小关系都严格遵守“左小右大”，所以整棵树的BST性质是数学上自然保持的。

3.4 迭代版：没有递归的返回值，就得自己维护parent

递归版简洁，但如果你想进一步理解指针操作，迭代版也别跳过：

TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) return new TreeNode(val); TreeNode* cur = root; while (cur) { if (val < cur->val) { if (cur->left == NULL) { cur->left = new TreeNode(val); break; } cur = cur->left; } else { if (cur->right == NULL) { cur->right = new TreeNode(val); break; } cur = cur->right; } } return root; }

这里最需要理解的是为什么要在“当前节点的孩子为空”时立刻处理，而不是等cur走到null再做。因为一旦cur变成null，你就不记得它的父节点是谁了，新节点不知道该往谁身上挂。递归版依靠函数调用栈天然保存父节点信息，迭代版必须自己创造条件：在空位出现前就停在上一个非空节点上。

3.5 我在这个题上踩过的坑

第一坑：递归调用后忘记用root->left接住返回值。当时我写的是insertIntoBST(root->left, val);，结果是新建的节点成了一个孤儿，根本没有任何指针指向它，提交后左子树莫名其妙少了一块。第二坑：迭代版里如果不用提前判断孩子是否为空，而是等cur走到null，就会丢失父节点信息。这两个坑其实只是同一个问题的两面：递归返回值要接住，迭代父节点要保存。

还有一个平时经常用的调试技巧：写一个中序遍历函数，插入后打印一遍，如果序列仍然严格升序，说明BST性质没有被破坏。这个方法性价比极高，后面几道题我也一直在用。

3.6 复杂度与隐藏延伸

插入操作的时间复杂度同样是O(h)。如果树是平衡的，h约为log n；但如果你按升序连续插入一串值，树会严重倾斜成链表状，h逼近n，这时插入效率就退化了。这也是后面AVL树、红黑树要解决的核心问题。701这题的叶子插入法虽然简单，但它让你切身感受到“查找路径”这个概念，为理解平衡树旋转打下了基础。

4. LC 450 删除节点：这道题真正考的是子树怎么重新连接

4.1 题目要求给了解题方向上的自由

450题要求从BST中删除指定key的节点，返回新的根。题目描述里有一句特别关键的话：树的结构可以改变，不必保持原来的样子，但必须仍然是BST。这句话等于给了解法很大的自由度，同时也暗示了题目难点：你需要的不是“找到一个节点删掉”，而是“删除后把周围的结构重新接好，且不破坏有序性”。

4.2 删除操作的完整情况枚举：一共就5种

不管你怎么实现，删除节点时一定会遇到以下五种情况之一：

前四种情况结构上都很简单，但有个小细节值得强调：当你把删除结果返回给父节点时，父节点必须接住这个返回值并更新自己的left或right。这里的逻辑和701的“粘合剂”完全一样。

4.3 左右都有孩子时，为什么必须用“中间值”替代

关键难点在第五种情况。待删节点有两棵子树，直接删除后，左子树和右子树之间需要一个节点来做“桥”，桥的值必须同时满足两个条件：大于左子树所有节点值，小于右子树所有节点值。BST里谁能满足？两个现成的候选人：右子树的最小节点，也就是右子树一路往左走到头的那个节点；或者左子树的最大节点，往右走到头的那个。它们正好夹在两棵子树中间，顶替上去之后有序性不会破坏。

我习惯选右子树的最小值，因为它还有一个额外好处：这个最左节点一定没有左孩子，删除它的时候会自然落到情况2或情况4里，处理起来非常省事。

4.4 两种替代实现：值传递法和指针重接法

方案一是值拷贝加递归删除：

TreeNode* deleteNode(TreeNode* root, int key) { if (root == NULL) return NULL; if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { if (root->left == NULL) return root->right; if (root->right == NULL) return root->left; TreeNode* minNode = root->right; while (minNode->left) minNode = minNode->left; root->val = minNode->val; root->right = deleteNode(root->right, minNode->val); } return root; }

这是最直观的写法：找到右子树最左节点，把它的值拷给root，然后递归去右子树里把这个值删除。因为最小节点很好删，所以递归深度可控。

方案二是指针重接法，代码更短：

TreeNode* deleteNode(TreeNode* root, int key) { if (root == NULL) return NULL; if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { if (root->left == NULL) return root->right; if (root->right == NULL) return root->left; TreeNode* minNode = root->right; while (minNode->left) minNode = minNode->left; minNode->left = root->left; return root->right; } return root; }

思路是把待删节点的左子树整体挂到右子树最小节点的左孩子上，然后直接返回右子树作为新的根。因为minNode一定没有左孩子，所以挂上去不会破坏右子树的有序性。这种写法代码简洁，但要小心：它容易让树变得更倾斜，长期做大量删除操作，树的形状会恶化。做题时两种都能AC，面试被追问时你需要能解释清楚两者的取舍。

4.5 迭代实现和递归的本质区别

递归版本之所以好写，是因为每个递归调用都能把自己的处理结果返回给上一层的父节点，父节点直接接住即可。迭代版本没有这个安全带，你必须自己维护父节点指针：

• 用cur指针找待删节点；
• 用pre指针记录cur的父节点；
• 删除后，根据cur是pre的左孩子还是右孩子，把新子树根赋给pre对应的孩子；
• 如果cur本身就是根，那删除结果直接作为新根返回。

这个版本写起来比递归繁琐，但能强迫你理解树结构改变的底层过程。我的建议是：先用递归把思路跑通，再尝试迭代；直接写迭代容易在指针的更新顺序里绕晕。

4.6 我在450上的三次提交过程

第一次提交，我只处理了叶子节点和空指针的情况，没有处理左右都有孩子的场景，挂在几个标准样例上。第二次提交，我学会了用右子树最小值替代，但只改了root的值，忘记递归删除右子树里的最小值，结果中序遍历打印出来出现了两个相同的key，BST性质被破坏。第三次提交才把“值拷贝之后还要继续递归删除源节点”这件事想完整，顺利通过。

这个过程中，打印中序遍历帮了大忙。每次删除完我都打印一遍序列，有重复值、序列乱序都能一眼看出来。

5. 刷完三道题的复盘：BST题目里那些“不说就会踩”的坑

5.1 递归函数返回值的“接住”意识

三道题看下来，我最大的收获是：凡是会修改树结构的BST递归，几乎都要写成“父节点孩子接住返回值”的模式。701里是root->left = insert(...)，450里是root->left = delete(...)，235虽然返回的是目标节点，但整个函数也是直接return每层的递归结果。这个模式可以总结成一句话：递归返回值要么被接住，要么被直接return，否则一定出问题。

很多人写树题时习惯把递归函数定义为void，改一个值就走人。但在BST这种需要重新连接父子关系的题里，void函数很容易丢信息。你需要的是一个能返回新子树根的TreeNode*函数。

5.2 空指针和防御性编程的优先级

BST题目对空指针极度敏感。我的经验是，递归入口先判root == NULL，相当于给所有调用上了保险；在450里判断左右孩子是否为NULL的顺序，直接决定接下来走哪个分支；迭代写法里则要在孩子为空之前停止前进，而不是让cur先变成NULL再去补救。把这三点养成肌肉记忆，这类题的bug至少能少一半。

5.3 中序遍历验证法：性价比最高的调试手段

BST题做完后，我强烈建议你在本地用中序遍历打印一遍结果。BST的性质决定了它的中序序列必须严格升序且不重复。删除或插入后一旦出现乱序、重复值，说明树结构已经被破坏了。

void inorder(TreeNode* root) { if (root == NULL) return; inorder(root->left); cout << root->val << " "; inorder(root->right); }

这招在450这类重结构题里特别管用。在线评测环境里你可以把打印临时加到测试代码里，本地观察；提交时再删掉就好。它不能直接告诉你哪里错，但能精确暴露“BST性质有没有坏”，帮你快速定位逻辑缺陷。

5.4 复杂度与树形退化：BST最性感也最脆弱

这三道题的操作复杂度都是O(h)。如果树平衡，h约等于log n，一切都很美好；但如果你按升序连续插入节点，树会不断右倾，最后退化成一个链表，h变成n，所有操作都变成线性时间。这个现象在450的指针重接方案里会更明显，因为每次把左子树挂到右子树最左节点的左孩子上，会让右子树深度变大。

面试时经常会被追问“如果插入序列有序会怎样”“BST为什么不能替代哈希表做查找”，本质上都是在问这个退化问题。Day16不需要把AVL、红黑树的旋转全部展开，但至少要在心里建立“BST天然优雅，但也会自我恶化”的认知。

5.5 给后续复习留下的几条线索

Day17我打算回头做98题验证BST，因为验证BST的核心就是用中序遍历判断是否严格升序，正好能复用这三道题的经验。之后还计划刷173题BST迭代器，那是用栈模拟中序遍历的进阶版本；以及538题把BST转换成累加树，本质上是在考察中序遍历的逆序应用。如果你也想安排后续计划，可以参考这个路线，围绕“中序有序性”和“递归返回值”两个点向外扩展。

把这三道题放在一起，我的整体感受是：BST题目本质上是在练习一种“剪枝思维”。普通二叉树的递归像在森林里漫无目的地搜索，BST则每走一步都知道自己为什么向左、为什么向右。235让我记住“夹在中间就是答案”，701让我记住“递归返回值要接住”，450让我记住“两棵子树接口处需要中间值补位”。下次再遇到BST题，我会先问自己三个问题：方向能不能判断？结构要不要改？返回值该往哪儿接。希望这份Day16复盘，能让你少踩一次我踩过的坑。