二叉树刷到LeetCode第21到29题很多人会进入一个相对别扭的阶段题目难度没有断崖式上升但题型突然变得“专项化”了。530、501、236、235、701、450、669、108、538这九道题不再像前二十题那样到处考察层序、直径、路径总和而是齐刷刷地围着二叉搜索树BST打转。这样的好处其实很大因为BST的题都有固定套路中序遍历有序、递归返回值、按值分治来回就是这几招。只要你把这九题看成一组来写而不是一道一道孤立地背题解很多“为什么这么写”的疑问会一下子解开。这篇笔记不适合完全零基础的朋友至少要把二叉树的前序遍历、中序、后序、递归建树搞明白再来。但如果你刷到一半卡在BST上或者好奇这几道题的内部联系那这篇文章正好可以当参考。我会把每个题的核心跳法、典型代码、复杂度、以及我实际写的时候踩过的坑全部拆开讲尽量不废话。1. 从21到29这九题其实是一个BST专项训练1.1 先看清题目是怎么分组的这九道题按操作类型可以分四类每一类都有自己非常明确的思维模型查询与统计530二叉搜索树的最小绝对差、501二叉搜索树中的众数、538把二叉搜索树转换为累加树。这三道题的核心都是“在遍历中聚合信息”而且遍历顺序直接决定解法难度。最近公共祖先236二叉树的最近公共祖先、235二叉搜索树的最近公共祖先。一道是普通二叉树一道是BST放在一起就是让你感受“约束条件”能给算法带来多大简化。动态维护701二叉搜索树中的插入操作、450删除二叉搜索树中的节点、669修剪二叉搜索树。这三道题考察的是如何在保持BST性质的前提下改树核心就是递归返回值如何把新的子树接回父节点。构造与改造108将有序数组转换为二叉搜索树、538累加树。一个是自顶向下建树一个是按特殊遍历序就地改值。这样一分你会发现组题的人是有心安排顺序的。530和501先让你熟悉“中序遍历BST就是有序序列”这个结论236和235再让你明白普通二叉树和BST在解题策略上的差异701、450、669连着三道增删改是希望你把“递归的返回值”这个基本功练扎实最后的108和538则是在前面所有套路之上延伸出构造和全局状态修改。1.2 贯穿这一组题的两个核心武器第一个武器是中序遍历。BST的中序遍历结果严格递增这是可以写在题目里的性质。很多看似复杂的统计题一旦转换成“在一个递增数组里处理相邻关系”难度会骤降。530要用到相邻差值501要用到连续相等区间538要用反向中序遍历实现从大到小累加全都是这一个性质的延伸。第二个武器是递归返回值的“接住”思想。在删除节点、修剪树、插入节点这些操作里递归函数处理完一棵子树后返回的是“处理后的新子树根”上层节点必须用 root-left 递归(...) 或者 root-right 递归(...) 来接收。这个习惯如果没养成写450的时候很容易出现“树改了但改的是个临时指针”这种幽灵问题。后面我会反复强调这个点。2. 530和501两兄弟把“中序遍历”玩明白了2.1 530 最小绝对差相邻差值的套路题目要求二叉搜索树中任意两个不同节点值之间的最小绝对差。一个最朴素的思路是把中序遍历的结果全部存到vector里然后扫描一遍相邻元素求最小差值。这样做完全没问题复杂度O(n)空间O(n)。但既然题目只需要相邻元素完全可以在中序遍历过程中只记录前一个节点的值不需要整个数组。这里的关键结论是最小差一定出现在中序序列的相邻元素之间。原因很简单中序序列是递增的比如 [1, 3, 6, 10]任意两个非相邻元素之间至少隔着两个相邻差值比如 10-1 9而相邻差里最小的是2非相邻差不可能比所有相邻差都小。所以在递归中留存一个pre指针每次访问当前节点时计算 node-val - pre 并更新答案即可。class Solution { public: int ans INT_MAX; long long pre LONG_MIN; // 用long long防止负值边界问题 int getMinimumDifference(TreeNode* root) { dfs(root); return ans; } void dfs(TreeNode* node) { if (!node) return; dfs(node-left); if (pre ! LONG_MIN) { ans min(ans, node-val - (int)pre); } pre node-val; dfs(node-right); } };一个小细节是pre的初始值。以前很多写法喜欢用-1但如果BST里恰好有节点值是-1就会出现“假差值”。稳妥的做法是用long long的最小值或者加一个bool变量记录是否已经访问过第一个节点。我在本地测试时用全局变量pre一个测试用例跑完忘记复位下一个用例直接崩溃这也是LeetCode上比较隐蔽的运行时错误来源之一。2.2 501 众数如何做到只扫一遍就收集全部众数BST里的众数指的是出现次数最多的节点值。因为中序序列递增所以相同的值一定是连续出现的。问题变成了“在一个递增数组里找出所有出现次数等于最大频次的连续段”。最直白的解法是两次中序遍历第一次算出最大出现次数maxCount第二次把出现次数等于maxCount的值全部收集。但还有更省事的单次遍历写法维护三个变量当前值curVal、当前值出现次数curCount、已经找到的最大次数maxCount。遍历时如果curCount大于maxCount说明之前收集的结果全部失效要清空后加入当前值如果等于maxCount说明当前值也是众数直接加入结果。class Solution { public: vectorint findMode(TreeNode* root) { vectorint ans; int maxCount 0, curCount 0; long long curVal LONG_MIN; bool first true; functionvoid(TreeNode*) dfs [](TreeNode* node) { if (!node) return; dfs(node-left); if (first) { curVal node-val; curCount 1; first false; } else { if (node-val curVal) { curCount; } else { curVal node-val; curCount 1; } } if (curCount maxCount) { maxCount curCount; ans.clear(); ans.push_back((int)curVal); } else if (curCount maxCount) { ans.push_back((int)curVal); } dfs(node-right); }; dfs(root); return ans; } };我当初第一次看到这个单次遍历写法时担心过一个case如果前面的元素曾经等于maxCount后面突然出现更大频率的元素清空之后会不会把中间的漏掉实际上不会因为一旦出现更大频次那才是真正的当前众数前面的低频元素本来就不该留在结果里。这个动态更新的逻辑是自洽的前提是遍历顺序必须保证相同元素连续出现而BST中序遍历正好满足。2.3 这两题合在一起看530和501的共同点在于都依赖“前一个节点/前一段区间的状态”。530用pre记录前一个值501用curVal和curCount记录当前连续区间。这种“维护遍历过程中的上下文变量”是BST统计题的通用技巧后续做累加树、判断BST合法性、求第k小节点值也都会用到。所以我建议把这两题的递归框架背下来特别是中序遍历的三段式先左、处理当前、再右任何需要按节点值顺序处理的题都可以套。3. 236和235从“无差别搜索”到“按值剪枝”3.1 236 最近公共祖先后序遍历的经典应用普通二叉树没有顺序约束要找p和q的最近公共祖先只能老老实实把整棵树摸一遍。常见递归写法非常短但逻辑其实很精巧TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || 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返回找到的那个节点如果子树里已经确定了公共祖先返回那个祖先。画一个实际场景体会一下。假设p在左子树q在右子树那么左递归返回p右递归返回q两层都不为空当前节点就是公共祖先。假设p是q的祖先那在进入左/右子树搜索时会先命中pp节点的递归直接返回p而它的父节点只有一侧有返回值另一侧是空因此父节点选择返回非空的那一侧也就是p。这样一路向上最后整个函数返回p正好符合“最近公共祖先是p”的结论。理解这个题最好放弃“跟着指针走”的直觉把它当成“两个子问题结果的汇总”。左右子树各返回一个节点当前节点负责判断这两个节点是不是分别来自不同侧。这也是普通二叉树题里少有的需要“后序收集信息”的题型建议画几个递归树手动跑一遍。3.2 235 最近公共祖先BST让搜索变成单路径同样是找最近公共祖先一旦树是BST问题就简单太多。核心判断依据是如果当前节点值严格介于p和q之间那p和q一定一个在左子树、一个在右子树当前节点就是最近公共祖先。如果当前节点值同时大于p和q那么p和q都在左子树里往左走同时小于就往右走。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 nullptr; }这段代码甚至不需要p和q谁大谁小因为用的全是同时大于和同时小于判断。如果root的值正好等于p或q那另一个节点一定在root的某个子树里此时当前节点就是祖先直接返回。复杂度的差异很明显236是O(n)235是O(h)h是树高。对于严重失衡的BSTh可能接近n但一般不会比236更差。3.3 相同目标不同约束解法天差地别把这两题放在一起刷最大的收获是约束条件就是算法情报。普通二叉树因为不知道下一步该往哪走只能全图搜索BST用了大小关系把“搜索”优化成了“路径查找”每一步都能排除一半子树。这个思想在后面的450、669里还会反复出现比如删除一个节点时如果key小于当前值那左子树里所有节点都小于当前值所以路径是唯一的不需要在右子树里浪费任何时间。4. 插入、删除与修剪递归返回值就是“连接线”4.1 701 插入操作新节点永远是挂到空位上插入BST最简单的做法是递归。每当遇到空节点就创建新节点返回。如果不是空节点比较val和当前节点的值决定往左递归还是往右递归并且把递归返回的结果赋值给当前节点的left或right。TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val root-val) { root-left insertIntoBST(root-left, val); } else if (val root-val) { root-right insertIntoBST(root-right, val); } return root; }为什么插入位置一定是叶子因为BST的插入逻辑从头到尾都在和现有节点比大小往左或往右的决策一直持续到遇到空指针。整个过程没有“旋转”或者“替换已有节点”的需求所以新建节点的父节点一定是一个原本存在的叶子节点。这里的根节点在绝大多数情况下不会变化除非整棵树本来就是空的。我见过不少人对这个递归返回值感到疑惑插入操作明明没有“改造”当前节点为什么还要 return root原因是递归的每一层都需要把“该子树处理后的根节点”告诉上一层否则上一层拿不到新创建的节点更不知道该怎么把它挂到自己的left或right上。仔细看代码root-left 递归调用 这个赋值才真正完成节点之间的连接。4.2 450 删除节点三种情况加“后继替换”删除是这九道题里最容易写崩的一道。难点在于删除之后还要继续保持BST性质而且被删除节点引用的结构调整比插入复杂得多。先按key比较当前节点决定去左子树还是右子树删。真正找到目标节点之后分三种情况目标节点没有孩子也就是叶子节点直接把root返回nullptr父节点的left或right就会变成空。目标节点只有一个孩子把唯一的那个孩子返回给父节点。这个孩子会顶替被删除节点的位置保证当前子树仍然满足BST性质。目标节点有两个孩子这是最麻烦的。常见做法是找右子树中最小的节点来替换当前节点也就是中序后继。右子树最小节点一定大于当前节点、小于右子树所有其他节点同时大于左子树全部节点用它替换不会破坏大小关系。实现时找到右子树最小节点后把它节点的值拷贝到当前节点然后去右子树里递归删除那个最小节点。这样原节点的物理位置会被新值覆盖同时右子树里的重复节点被清掉。TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; 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 !root-right) { return nullptr; } if (!root-left) { return root-right; } if (!root-right) { return root-left; } TreeNode* successor root-right; while (successor-left) { successor successor-left; } root-val successor-val; root-right deleteNode(root-right, successor-val); } return root; }这里的细节是删除后继节点时一定不会出现“两个孩子的复杂情况”因为右子树最小节点如果有左孩子那就不是最小了。所以递归调用会走到叶子或单孩子分支处理起来很干净。如果你选择用左子树最大节点替换也是同理甚至也可以直接把后继节点摘下来接到root位置但那样需要处理的孩子指针更多新手不建议。4.3 669 修剪BST先丢根再修枝修剪的核心是区间 [low, high]。如果当前节点值小于low那么当前节点本身以及它的整个左子树都不可能留在结果里唯一可能藏在右子树中所以直接返回“修剪后的右子树”。如果当前节点值大于high就对称地返回“修剪后的左子树”。只有当前节点在区间内时才需要分别修剪它的左右子树然后收好返回的新根。TreeNode* trimBST(TreeNode* root, int low, int high) { if (!root) return nullptr; if (root-val low) { return trimBST(root-right, low, high); } if (root-val high) { return trimBST(root-left, low, high); } root-left trimBST(root-left, low, high); root-right trimBST(root-right, low, high); return root; }很多新手容易犯的错是当root值小于low时只 remove 左子树留下当前根节点。这是不对的因为当前节点本身也不满足 low 的约束必须连根一起丢掉让修剪后的右子树直接上位。如果拿450和669对比会发现两者有一个共同模式当前节点“不合格”时用某个孩子结果替换当前节点当前节点合格时递归处理孩子并用返回值接住。这种行为上的相似性不是偶然它们都是“递归返回值驱动树结构变化”的例证。4.4 为什么递归返回值在这种题目里像“连接线”插入、删除、修剪这三题代码里都出现了大量 root-left 递归(...) 和 root-right 递归(...) 的赋值动作。递归调用真正修改的是“当前这棵子树的根”而上层函数通过返回值知道新的根是谁。如果不做赋值只在函数内部改一个局部变量那父节点的指针永远不会更新树的结构自然也不会变。这可能是所有二叉树增删改题里最核心的一个顿悟点。你觉得“函数已经把根改好了”其实在C默认传指针拷贝的情况下你只改了副本指向的堆内存里的字段并没有改父节点指针本身所以必须把返回值一路向上传。理解了这条连接线450和669的代码就只是一层简单封装而已。5. 108和538构造树与重写树的两个方向5.1 108 有序数组转平衡BST二分递归建树有序数组本质上就是BST的中序序列。要把它构造成一棵平衡BST最稳妥的办法是每次取数组区间的中间元素作为根。这样左半部分天然是左子树的元素集合右半部分是右子树的元素集合递归下去左右子树的高度差不会超过1。TreeNode* sortedArrayToBST(vectorint nums) { return build(nums, 0, nums.size() - 1); } TreeNode* build(vectorint nums, int left, int right) { if (left right) return nullptr; int mid left (right - left) / 2; TreeNode* root new TreeNode(nums[mid]); root-left build(nums, left, mid - 1); root-right build(nums, mid 1, right); return root; }这里有三个值得注意的细节。第一用 left (right - left) / 2 而不是 (left right) / 2虽然对int不容易溢出但养成好习惯总归没错。第二递归边界是 left right 而不是 left right否则会漏掉单个节点的情况。第三因为数组有序所以不需要考虑“数组中相等元素怎么分配”的问题任意一个中间位置都能保证正确性如果想得到最平衡的树mid取中点即可。最终复杂度O(n)每个节点只被构建一次。5.2 538 累加树反中序遍历维护全局和题目要求把每个节点的值改成“原树中大于或等于该节点值的所有节点值之和”。BST中序遍历是从小到大如果我们倒过来先走右子树再访问当前节点最后走左子树得到的访问顺序就是从大到小。维护一个全局sum每次访问当前节点时先把当前值加进sum然后把当前节点值改成sum。这样对于任意节点在访问它之前sum已经收集了所有比它大的节点值。class Solution { public: int sum 0; TreeNode* convertBST(TreeNode* root) { if (!root) return nullptr; convertBST(root-right); sum root-val; root-val sum; convertBST(root-left); return root; } };注意这题的遍历顺序绝对不能写反。如果用中序正序sum累加的是比当前值小的和那就变成累加树的反方向了。我当时第一次写就没转过弯来把右递归和左递归交换了一下运行结果完全不对后来画了一个三层BST才想明白因为大于等于当前值的节点全部集中在当前节点的右侧和祖先的右侧链上只有反中序才能在访问一个节点时保证这些值都已经被处理过。5.3 构造与重写的常用模板108是典型的自顶向下构造每次确定根节点递归创建子树创建的根返回给上一层。538是典型的遍历中修改不改变树形只在访问节点时更新值。这两种模式在二叉树题目里非常常见。构造题目往往需要一个“区间”参数描述子树的元素范围修改题目往往需要一个外部全局变量在遍历过程中传递状态。把这层外壳剥掉剩下的还是熟悉的递归骨架处理当前节点递归处理子树必要时把结果返回上层。6. 实操心得与常见报错排查6.1 为什么BST递归题老是在LeetCode上报运行时错误“运行时错误”四个字在BST题里九成是空指针访问剩下的一成是栈溢出。空指针访问的典型场景是递归到空节点后只判断了node是否为空就忘了判断node-left是否为空就直接访问node-left-val。另一个更隐蔽的是全局变量初始化问题。我在本地调试时定义了一个类成员变量pre连续跑多个测试用例上一个用例跑完后pre还保留着旧值导致下一个用例的第一个判断就出错。LeetCode每个测试用例一般会新建类的实例不容易踩这个坑但自己用同一个对象测试多个用例就会遇到。栈溢出则通常发生在树退化成链的时候。比如按有序顺序反复插入节点BST会变成一条链递归深度达到nn稍微大一点就会爆栈。刷题阶段最实用的解决办法是保持递归写法但注意题目给出的数据规模如果是n10^5级别且树可能退化的题优先考虑迭代。幸运的是这九道题在正常LeetCode约束下递归都能过。6.2 用错返回值和漏掉赋值的三个高频坑我总结一下自己遇到的、以及帮别人排查时经常看到的三个坑。第一个坑是删除和修剪时没有接收递归返回值。很多人写 if (key root-val) deleteNode(root-left, key); 然后发现节点没删掉。原因就是更新后的子树根没有重新挂到root-left上旧地址指向的节点明明被释放或改变了关系父节点却不知情。第二个坑是两个孩子的删除节点里先把右子树最小节点的值复制过来但没有递归删除那个最小节点结果树里出现两个相同值的节点。记住赋完值之后一定要在右子树里再调用一次deleteNode把旧后继节点清掉。第三个坑是修剪时只看孩子不看根。root的值本身小于low或大于high时直接把root丢给修剪函数处理保留root本身最终结果里会出现越界节点。修剪和删除不同删除可以保留符合条件的根修剪中“根不符合区间”时必须整节点替换。6.3 一个顺手的调试手法和几道题的注意事项我自己调试BST递归题时最常用的方法不是打日志而是写一个“收集中序结果”的函数输出当前树的顺序。因为BST性质是否被破坏用中序遍历结果一眼就能看出来。删除和修剪后如果中序序列不是递增的说明指针接错了如果是递增但数值不对说明替换值选错了。再补充几个零碎经验530里不要用INT_MIN做哨兵如果节点差值和INT_MIN有关会溢出建议用long long存pre最后强转int501里如果题目说最多只有一个众数那还可以写得再简单些但按LeetCode原题可能不止一个务必保留结果列表701里如果val和已有节点值相等有的语言会直接返回root有的会挂到右边建议看题目前提若没提默认不处理重复值。450中替代节点用右子树最小还是左子树最大都行但要在一道题内保持一致不要一会儿用后继一会儿用前驱。这九道题刷完之后我自己最明显的感受是BST其实是一类相当“有礼貌”的树它愿意把答案放在你能预测的位置最小值在最左最大值在最右中序遍历有序上下界由节点大小决定。你要做的只是顺着这些规则走。很多递归它在规划时我就觉得繁琐但上手调试过几次特别是把450和669的递归返回值逻辑亲手改对之后再看后面的AVL、红黑树代码至少对“为什么调整完要返回新根”这件事有了特别深的体感。如果让我只留一个建议那就是把这套“中序遍历递归返回值”的写法吃透以后不管遇到BST的什么变形题你都能比别人更快找到入手点。 
长河君 · 2026/10/9 4:06:46 · 阅读 1.2k BST专项：中序遍历+递归返回值破解LeetCode 21-29题
二叉树刷到LeetCode第21到29题很多人会进入一个相对别扭的阶段题目难度没有断崖式上升但题型突然变得“专项化”了。530、501、236、235、701、450、669、108、538这九道题不再像前二十题那样到处考察层序、直径、路径总和而是齐刷刷地围着二叉搜索树BST打转。这样的好处其实很大因为BST的题都有固定套路中序遍历有序、递归返回值、按值分治来回就是这几招。只要你把这九题看成一组来写而不是一道一道孤立地背题解很多“为什么这么写”的疑问会一下子解开。这篇笔记不适合完全零基础的朋友至少要把二叉树的前序遍历、中序、后序、递归建树搞明白再来。但如果你刷到一半卡在BST上或者好奇这几道题的内部联系那这篇文章正好可以当参考。我会把每个题的核心跳法、典型代码、复杂度、以及我实际写的时候踩过的坑全部拆开讲尽量不废话。1. 从21到29这九题其实是一个BST专项训练1.1 先看清题目是怎么分组的这九道题按操作类型可以分四类每一类都有自己非常明确的思维模型查询与统计530二叉搜索树的最小绝对差、501二叉搜索树中的众数、538把二叉搜索树转换为累加树。这三道题的核心都是“在遍历中聚合信息”而且遍历顺序直接决定解法难度。最近公共祖先236二叉树的最近公共祖先、235二叉搜索树的最近公共祖先。一道是普通二叉树一道是BST放在一起就是让你感受“约束条件”能给算法带来多大简化。动态维护701二叉搜索树中的插入操作、450删除二叉搜索树中的节点、669修剪二叉搜索树。这三道题考察的是如何在保持BST性质的前提下改树核心就是递归返回值如何把新的子树接回父节点。构造与改造108将有序数组转换为二叉搜索树、538累加树。一个是自顶向下建树一个是按特殊遍历序就地改值。这样一分你会发现组题的人是有心安排顺序的。530和501先让你熟悉“中序遍历BST就是有序序列”这个结论236和235再让你明白普通二叉树和BST在解题策略上的差异701、450、669连着三道增删改是希望你把“递归的返回值”这个基本功练扎实最后的108和538则是在前面所有套路之上延伸出构造和全局状态修改。1.2 贯穿这一组题的两个核心武器第一个武器是中序遍历。BST的中序遍历结果严格递增这是可以写在题目里的性质。很多看似复杂的统计题一旦转换成“在一个递增数组里处理相邻关系”难度会骤降。530要用到相邻差值501要用到连续相等区间538要用反向中序遍历实现从大到小累加全都是这一个性质的延伸。第二个武器是递归返回值的“接住”思想。在删除节点、修剪树、插入节点这些操作里递归函数处理完一棵子树后返回的是“处理后的新子树根”上层节点必须用 root-left 递归(...) 或者 root-right 递归(...) 来接收。这个习惯如果没养成写450的时候很容易出现“树改了但改的是个临时指针”这种幽灵问题。后面我会反复强调这个点。2. 530和501两兄弟把“中序遍历”玩明白了2.1 530 最小绝对差相邻差值的套路题目要求二叉搜索树中任意两个不同节点值之间的最小绝对差。一个最朴素的思路是把中序遍历的结果全部存到vector里然后扫描一遍相邻元素求最小差值。这样做完全没问题复杂度O(n)空间O(n)。但既然题目只需要相邻元素完全可以在中序遍历过程中只记录前一个节点的值不需要整个数组。这里的关键结论是最小差一定出现在中序序列的相邻元素之间。原因很简单中序序列是递增的比如 [1, 3, 6, 10]任意两个非相邻元素之间至少隔着两个相邻差值比如 10-1 9而相邻差里最小的是2非相邻差不可能比所有相邻差都小。所以在递归中留存一个pre指针每次访问当前节点时计算 node-val - pre 并更新答案即可。class Solution { public: int ans INT_MAX; long long pre LONG_MIN; // 用long long防止负值边界问题 int getMinimumDifference(TreeNode* root) { dfs(root); return ans; } void dfs(TreeNode* node) { if (!node) return; dfs(node-left); if (pre ! LONG_MIN) { ans min(ans, node-val - (int)pre); } pre node-val; dfs(node-right); } };一个小细节是pre的初始值。以前很多写法喜欢用-1但如果BST里恰好有节点值是-1就会出现“假差值”。稳妥的做法是用long long的最小值或者加一个bool变量记录是否已经访问过第一个节点。我在本地测试时用全局变量pre一个测试用例跑完忘记复位下一个用例直接崩溃这也是LeetCode上比较隐蔽的运行时错误来源之一。2.2 501 众数如何做到只扫一遍就收集全部众数BST里的众数指的是出现次数最多的节点值。因为中序序列递增所以相同的值一定是连续出现的。问题变成了“在一个递增数组里找出所有出现次数等于最大频次的连续段”。最直白的解法是两次中序遍历第一次算出最大出现次数maxCount第二次把出现次数等于maxCount的值全部收集。但还有更省事的单次遍历写法维护三个变量当前值curVal、当前值出现次数curCount、已经找到的最大次数maxCount。遍历时如果curCount大于maxCount说明之前收集的结果全部失效要清空后加入当前值如果等于maxCount说明当前值也是众数直接加入结果。class Solution { public: vectorint findMode(TreeNode* root) { vectorint ans; int maxCount 0, curCount 0; long long curVal LONG_MIN; bool first true; functionvoid(TreeNode*) dfs [](TreeNode* node) { if (!node) return; dfs(node-left); if (first) { curVal node-val; curCount 1; first false; } else { if (node-val curVal) { curCount; } else { curVal node-val; curCount 1; } } if (curCount maxCount) { maxCount curCount; ans.clear(); ans.push_back((int)curVal); } else if (curCount maxCount) { ans.push_back((int)curVal); } dfs(node-right); }; dfs(root); return ans; } };我当初第一次看到这个单次遍历写法时担心过一个case如果前面的元素曾经等于maxCount后面突然出现更大频率的元素清空之后会不会把中间的漏掉实际上不会因为一旦出现更大频次那才是真正的当前众数前面的低频元素本来就不该留在结果里。这个动态更新的逻辑是自洽的前提是遍历顺序必须保证相同元素连续出现而BST中序遍历正好满足。2.3 这两题合在一起看530和501的共同点在于都依赖“前一个节点/前一段区间的状态”。530用pre记录前一个值501用curVal和curCount记录当前连续区间。这种“维护遍历过程中的上下文变量”是BST统计题的通用技巧后续做累加树、判断BST合法性、求第k小节点值也都会用到。所以我建议把这两题的递归框架背下来特别是中序遍历的三段式先左、处理当前、再右任何需要按节点值顺序处理的题都可以套。3. 236和235从“无差别搜索”到“按值剪枝”3.1 236 最近公共祖先后序遍历的经典应用普通二叉树没有顺序约束要找p和q的最近公共祖先只能老老实实把整棵树摸一遍。常见递归写法非常短但逻辑其实很精巧TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || 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返回找到的那个节点如果子树里已经确定了公共祖先返回那个祖先。画一个实际场景体会一下。假设p在左子树q在右子树那么左递归返回p右递归返回q两层都不为空当前节点就是公共祖先。假设p是q的祖先那在进入左/右子树搜索时会先命中pp节点的递归直接返回p而它的父节点只有一侧有返回值另一侧是空因此父节点选择返回非空的那一侧也就是p。这样一路向上最后整个函数返回p正好符合“最近公共祖先是p”的结论。理解这个题最好放弃“跟着指针走”的直觉把它当成“两个子问题结果的汇总”。左右子树各返回一个节点当前节点负责判断这两个节点是不是分别来自不同侧。这也是普通二叉树题里少有的需要“后序收集信息”的题型建议画几个递归树手动跑一遍。3.2 235 最近公共祖先BST让搜索变成单路径同样是找最近公共祖先一旦树是BST问题就简单太多。核心判断依据是如果当前节点值严格介于p和q之间那p和q一定一个在左子树、一个在右子树当前节点就是最近公共祖先。如果当前节点值同时大于p和q那么p和q都在左子树里往左走同时小于就往右走。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 nullptr; }这段代码甚至不需要p和q谁大谁小因为用的全是同时大于和同时小于判断。如果root的值正好等于p或q那另一个节点一定在root的某个子树里此时当前节点就是祖先直接返回。复杂度的差异很明显236是O(n)235是O(h)h是树高。对于严重失衡的BSTh可能接近n但一般不会比236更差。3.3 相同目标不同约束解法天差地别把这两题放在一起刷最大的收获是约束条件就是算法情报。普通二叉树因为不知道下一步该往哪走只能全图搜索BST用了大小关系把“搜索”优化成了“路径查找”每一步都能排除一半子树。这个思想在后面的450、669里还会反复出现比如删除一个节点时如果key小于当前值那左子树里所有节点都小于当前值所以路径是唯一的不需要在右子树里浪费任何时间。4. 插入、删除与修剪递归返回值就是“连接线”4.1 701 插入操作新节点永远是挂到空位上插入BST最简单的做法是递归。每当遇到空节点就创建新节点返回。如果不是空节点比较val和当前节点的值决定往左递归还是往右递归并且把递归返回的结果赋值给当前节点的left或right。TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val root-val) { root-left insertIntoBST(root-left, val); } else if (val root-val) { root-right insertIntoBST(root-right, val); } return root; }为什么插入位置一定是叶子因为BST的插入逻辑从头到尾都在和现有节点比大小往左或往右的决策一直持续到遇到空指针。整个过程没有“旋转”或者“替换已有节点”的需求所以新建节点的父节点一定是一个原本存在的叶子节点。这里的根节点在绝大多数情况下不会变化除非整棵树本来就是空的。我见过不少人对这个递归返回值感到疑惑插入操作明明没有“改造”当前节点为什么还要 return root原因是递归的每一层都需要把“该子树处理后的根节点”告诉上一层否则上一层拿不到新创建的节点更不知道该怎么把它挂到自己的left或right上。仔细看代码root-left 递归调用 这个赋值才真正完成节点之间的连接。4.2 450 删除节点三种情况加“后继替换”删除是这九道题里最容易写崩的一道。难点在于删除之后还要继续保持BST性质而且被删除节点引用的结构调整比插入复杂得多。先按key比较当前节点决定去左子树还是右子树删。真正找到目标节点之后分三种情况目标节点没有孩子也就是叶子节点直接把root返回nullptr父节点的left或right就会变成空。目标节点只有一个孩子把唯一的那个孩子返回给父节点。这个孩子会顶替被删除节点的位置保证当前子树仍然满足BST性质。目标节点有两个孩子这是最麻烦的。常见做法是找右子树中最小的节点来替换当前节点也就是中序后继。右子树最小节点一定大于当前节点、小于右子树所有其他节点同时大于左子树全部节点用它替换不会破坏大小关系。实现时找到右子树最小节点后把它节点的值拷贝到当前节点然后去右子树里递归删除那个最小节点。这样原节点的物理位置会被新值覆盖同时右子树里的重复节点被清掉。TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; 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 !root-right) { return nullptr; } if (!root-left) { return root-right; } if (!root-right) { return root-left; } TreeNode* successor root-right; while (successor-left) { successor successor-left; } root-val successor-val; root-right deleteNode(root-right, successor-val); } return root; }这里的细节是删除后继节点时一定不会出现“两个孩子的复杂情况”因为右子树最小节点如果有左孩子那就不是最小了。所以递归调用会走到叶子或单孩子分支处理起来很干净。如果你选择用左子树最大节点替换也是同理甚至也可以直接把后继节点摘下来接到root位置但那样需要处理的孩子指针更多新手不建议。4.3 669 修剪BST先丢根再修枝修剪的核心是区间 [low, high]。如果当前节点值小于low那么当前节点本身以及它的整个左子树都不可能留在结果里唯一可能藏在右子树中所以直接返回“修剪后的右子树”。如果当前节点值大于high就对称地返回“修剪后的左子树”。只有当前节点在区间内时才需要分别修剪它的左右子树然后收好返回的新根。TreeNode* trimBST(TreeNode* root, int low, int high) { if (!root) return nullptr; if (root-val low) { return trimBST(root-right, low, high); } if (root-val high) { return trimBST(root-left, low, high); } root-left trimBST(root-left, low, high); root-right trimBST(root-right, low, high); return root; }很多新手容易犯的错是当root值小于low时只 remove 左子树留下当前根节点。这是不对的因为当前节点本身也不满足 low 的约束必须连根一起丢掉让修剪后的右子树直接上位。如果拿450和669对比会发现两者有一个共同模式当前节点“不合格”时用某个孩子结果替换当前节点当前节点合格时递归处理孩子并用返回值接住。这种行为上的相似性不是偶然它们都是“递归返回值驱动树结构变化”的例证。4.4 为什么递归返回值在这种题目里像“连接线”插入、删除、修剪这三题代码里都出现了大量 root-left 递归(...) 和 root-right 递归(...) 的赋值动作。递归调用真正修改的是“当前这棵子树的根”而上层函数通过返回值知道新的根是谁。如果不做赋值只在函数内部改一个局部变量那父节点的指针永远不会更新树的结构自然也不会变。这可能是所有二叉树增删改题里最核心的一个顿悟点。你觉得“函数已经把根改好了”其实在C默认传指针拷贝的情况下你只改了副本指向的堆内存里的字段并没有改父节点指针本身所以必须把返回值一路向上传。理解了这条连接线450和669的代码就只是一层简单封装而已。5. 108和538构造树与重写树的两个方向5.1 108 有序数组转平衡BST二分递归建树有序数组本质上就是BST的中序序列。要把它构造成一棵平衡BST最稳妥的办法是每次取数组区间的中间元素作为根。这样左半部分天然是左子树的元素集合右半部分是右子树的元素集合递归下去左右子树的高度差不会超过1。TreeNode* sortedArrayToBST(vectorint nums) { return build(nums, 0, nums.size() - 1); } TreeNode* build(vectorint nums, int left, int right) { if (left right) return nullptr; int mid left (right - left) / 2; TreeNode* root new TreeNode(nums[mid]); root-left build(nums, left, mid - 1); root-right build(nums, mid 1, right); return root; }这里有三个值得注意的细节。第一用 left (right - left) / 2 而不是 (left right) / 2虽然对int不容易溢出但养成好习惯总归没错。第二递归边界是 left right 而不是 left right否则会漏掉单个节点的情况。第三因为数组有序所以不需要考虑“数组中相等元素怎么分配”的问题任意一个中间位置都能保证正确性如果想得到最平衡的树mid取中点即可。最终复杂度O(n)每个节点只被构建一次。5.2 538 累加树反中序遍历维护全局和题目要求把每个节点的值改成“原树中大于或等于该节点值的所有节点值之和”。BST中序遍历是从小到大如果我们倒过来先走右子树再访问当前节点最后走左子树得到的访问顺序就是从大到小。维护一个全局sum每次访问当前节点时先把当前值加进sum然后把当前节点值改成sum。这样对于任意节点在访问它之前sum已经收集了所有比它大的节点值。class Solution { public: int sum 0; TreeNode* convertBST(TreeNode* root) { if (!root) return nullptr; convertBST(root-right); sum root-val; root-val sum; convertBST(root-left); return root; } };注意这题的遍历顺序绝对不能写反。如果用中序正序sum累加的是比当前值小的和那就变成累加树的反方向了。我当时第一次写就没转过弯来把右递归和左递归交换了一下运行结果完全不对后来画了一个三层BST才想明白因为大于等于当前值的节点全部集中在当前节点的右侧和祖先的右侧链上只有反中序才能在访问一个节点时保证这些值都已经被处理过。5.3 构造与重写的常用模板108是典型的自顶向下构造每次确定根节点递归创建子树创建的根返回给上一层。538是典型的遍历中修改不改变树形只在访问节点时更新值。这两种模式在二叉树题目里非常常见。构造题目往往需要一个“区间”参数描述子树的元素范围修改题目往往需要一个外部全局变量在遍历过程中传递状态。把这层外壳剥掉剩下的还是熟悉的递归骨架处理当前节点递归处理子树必要时把结果返回上层。6. 实操心得与常见报错排查6.1 为什么BST递归题老是在LeetCode上报运行时错误“运行时错误”四个字在BST题里九成是空指针访问剩下的一成是栈溢出。空指针访问的典型场景是递归到空节点后只判断了node是否为空就忘了判断node-left是否为空就直接访问node-left-val。另一个更隐蔽的是全局变量初始化问题。我在本地调试时定义了一个类成员变量pre连续跑多个测试用例上一个用例跑完后pre还保留着旧值导致下一个用例的第一个判断就出错。LeetCode每个测试用例一般会新建类的实例不容易踩这个坑但自己用同一个对象测试多个用例就会遇到。栈溢出则通常发生在树退化成链的时候。比如按有序顺序反复插入节点BST会变成一条链递归深度达到nn稍微大一点就会爆栈。刷题阶段最实用的解决办法是保持递归写法但注意题目给出的数据规模如果是n10^5级别且树可能退化的题优先考虑迭代。幸运的是这九道题在正常LeetCode约束下递归都能过。6.2 用错返回值和漏掉赋值的三个高频坑我总结一下自己遇到的、以及帮别人排查时经常看到的三个坑。第一个坑是删除和修剪时没有接收递归返回值。很多人写 if (key root-val) deleteNode(root-left, key); 然后发现节点没删掉。原因就是更新后的子树根没有重新挂到root-left上旧地址指向的节点明明被释放或改变了关系父节点却不知情。第二个坑是两个孩子的删除节点里先把右子树最小节点的值复制过来但没有递归删除那个最小节点结果树里出现两个相同值的节点。记住赋完值之后一定要在右子树里再调用一次deleteNode把旧后继节点清掉。第三个坑是修剪时只看孩子不看根。root的值本身小于low或大于high时直接把root丢给修剪函数处理保留root本身最终结果里会出现越界节点。修剪和删除不同删除可以保留符合条件的根修剪中“根不符合区间”时必须整节点替换。6.3 一个顺手的调试手法和几道题的注意事项我自己调试BST递归题时最常用的方法不是打日志而是写一个“收集中序结果”的函数输出当前树的顺序。因为BST性质是否被破坏用中序遍历结果一眼就能看出来。删除和修剪后如果中序序列不是递增的说明指针接错了如果是递增但数值不对说明替换值选错了。再补充几个零碎经验530里不要用INT_MIN做哨兵如果节点差值和INT_MIN有关会溢出建议用long long存pre最后强转int501里如果题目说最多只有一个众数那还可以写得再简单些但按LeetCode原题可能不止一个务必保留结果列表701里如果val和已有节点值相等有的语言会直接返回root有的会挂到右边建议看题目前提若没提默认不处理重复值。450中替代节点用右子树最小还是左子树最大都行但要在一道题内保持一致不要一会儿用后继一会儿用前驱。这九道题刷完之后我自己最明显的感受是BST其实是一类相当“有礼貌”的树它愿意把答案放在你能预测的位置最小值在最左最大值在最右中序遍历有序上下界由节点大小决定。你要做的只是顺着这些规则走。很多递归它在规划时我就觉得繁琐但上手调试过几次特别是把450和669的递归返回值逻辑亲手改对之后再看后面的AVL、红黑树代码至少对“为什么调整完要返回新根”这件事有了特别深的体感。如果让我只留一个建议那就是把这套“中序遍历递归返回值”的写法吃透以后不管遇到BST的什么变形题你都能比别人更快找到入手点。