LeetCode 538：二叉搜索树转累加树的反向中序遍历与莫里斯优化

刷 LeetCode 刷到 538 这道题的时候很多人的第一反应是又是二叉树遍历但看清“把二叉搜索树转换为累加树”这句话又有点懵。二叉搜索树熟累加树是什么我第一次做这题的时候甚至先去搜了一下定义结果发现它就是在原有二叉搜索树上原地改值每个节点要变成“大于等于它自己的所有节点值之和”。这题表面考树的遍历实际考的是对二叉搜索树有序性的敏感度。整道题不需要建新树、不需要排序、不需要额外数组核心代码写出来可能不到十行但能把递归、迭代、莫里斯遍历三种思路串在一起讲清楚。这篇文章就把这题的来龙去脉、实现细节和常见翻车点一次性讲透。顺便说一句搜索“累加树”的时候可能会看到“最优二叉搜索树”之类的关联词那是另一类研究查询频率的动态规划问题和 LeetCode 538 完全不是一回事别被带偏。1. 先把题意翻译成人话累加树到底在累加哪些节点的值1.1 二叉搜索树的性质就是整个题目的题眼要理解累加树得先回到二叉搜索树本身。二叉搜索树BST要求每个节点都满足左子树所有节点的值小于当前节点右子树所有节点的值大于当前节点。这个约束带来一个极其重要的结论对 BST 做中序遍历左-根-右得到的序列是严格递增的。累加树Greater Sum Tree的定义是在原树上做一次整体替换把每个节点的值改成原树中所有不小于当前节点值的节点值之和。注意“不小于”包含它自己。举个例子假如某个节点的原值是 3而整棵树里值大于等于 3 的节点分别是 3、5、8那么转换后这个节点的值就是 16。最大值节点因为没有比它更大的值转换后保持不变这一点可以当验证条件用。LeetCode 给的标准用例是这样的输入 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8 输出 30 / \ 36 21 / \ / \ 36 35 26 15 \ \ 33 8手动验算一下8 是最大值保持 87 加 8 等于 156 加 7 加 8 等于 215 加 6 加 7 加 8 等于 26一路累加1 加 2 加 3 一直到 8 等于 36。输出树的每个节点值正好就是原树中从该节点到最大值这条“后缀路径”的和。1.2 为什么“先求总和再逐个减”的方案也能做但不推荐看到这个定义后很多人的第一版思路是这样的先遍历整棵树求出所有节点的总和然后按升序遍历节点每走到一个节点就用总和减去它之前所有节点的值。这个思路对不对对。因为“所有大于等于当前节点的值之和”等价于“总和减去所有小于当前节点的值之和”。比如原树总和是 36当前节点是 0小于它的节点没有所以它转换后是 36当前节点是 2小于它的节点有 0 和 1所以转换结果是 36 减 1 等于 35。但我不推荐这种写法。原因有三个第一它需要额外维护一个“已被减掉的值”遍历顺序、求和逻辑和赋值逻辑混在一起容易把变量搞混。第二它必须保证先完整求一次总和这意味着至少需要遍历两遍树虽然时间复杂度仍然是 O(n)但常数更大代码也更绕。第三面试官如果追问“能不能只遍历一遍”你还是要回到反中序遍历的思路上不如一开始就用对方向。1.3 这题真正想考察的能力是什么LeetCode 的 Easy 和 Medium 题里很多题目表面上在问“能不能实现某个功能”实际在问“你能不能看穿数据结构背后的顺序关系”。538 就是典型它想让你发现累加树的构建过程本质上就是一次从大到小的中序遍历。BST 的中序序列是升序的那降序序列是什么就是中序遍历的镜像先访问右子树再访问根节点最后访问左子树也就是“右-根-左”顺序。这个顺序恰恰是从最大值一路走到最小值的顺序和累加需要的顺序完全吻合。如果能理解到这一层这道题的核心就已经拿下了。剩下的只是怎么把“边遍历边累加”落到代码上。2. 核心思路把遍历顺序反过来问题瞬间变得简单2.1 从升序到降序只差一个镜像操作中序遍历的递归写法是大家最熟的处理左子树 - 处理当前节点 - 处理右子树现在要把节点值改成一个后缀和而“后缀”的方向是从大到小所以遍历顺序必须反过来处理右子树 - 处理当前节点 - 处理左子树我把这个顺序称为“反向中序遍历”也有人叫“右根左遍历”。在反向中序遍历的过程中维护一个累加变量sum每访问到一个节点先把sum加上当前节点的原值再把累加结果赋给当前节点。因为遍历顺序保证“所有比当前节点大的节点都已经被访问过”所以sum正好就是所有不小于当前节点值的节点值之和。可以把这个过程想象成一群人按身高从高到矮排队每个人进场时报告前面所有人的身高总和然后把自己的身高加进这个总和里。排在最后的最矮的人听到的是全场所有人的身高和。BST 的节点就是这支队伍反向中序遍历就是让它们从大到小依次进场。2.2 累加变量是如何从右到左贯穿整棵树的细看一棵树的遍历过程会更清楚。以根节点 4、右子树 6、左子树 2 这样一棵简单 BST 为例4 / \ 2 6反向中序遍历顺序是6 - 4 - 2。先进入右子树节点 6sum从 0 变成 6节点值改成 6回到根节点 4sum从 6 变成 10节点值改成 10再进入左子树节点 2sum从 10 变成 12节点值改成 12。转换后10 / \ 12 6检查一下6 本来就是最大值没有比自己更大的节点所以保持 64 的右边只有 6所以变成 102 右边有 4 和 6所以变成 12。完全正确。注意到一个细节累加变量sum不是跟着递归路径“垂直”传递的而是跟着访问顺序“水平”流动的。从最右侧的叶子节点开始一路向左扫过去。在整个遍历过程中sum只增不减是一个与树结构无关的单调递增标量。2.3 反向中序的三个等价说法反向中序、右根左、降序序列这三个说法本质上是同一个东西在不同场合下会以不同形式出现。刷题时如果你能快速在它们之间切换看题解会轻松很多反向中序描述的是递归结构先右后左右根左描述的是访问顺序三个字直接说出来降序序列描述的是输出结果对应到数组上就是非递增序列。这道题里还有一个等价说法“后缀和”。如果把二叉搜索树中序遍历得到的升序数组记为[a1, a2, ..., an]累加树要做的就是把每个位置上的值变成ai a(i1) ... an。看到这里你应该明白了538 本质上是把“数组后缀和”问题搬到了二叉搜索树上利用中序遍历的有序性把树的遍历变成数组的滑动累加。这个视角最大的价值在于以后遇到“把二叉搜索树转换成 XXX 树”的题目先想想数组版本是怎么做的再想想遍历顺序应该怎么调整思路会比直接硬写递归清晰得多。3. 递归解法从全局变量到函数式传参两种写法实测对比3.1 全局变量写法最直观但要小心状态残留先给出绝大多数题解都会采用的版本Python 代码class Solution: def convertBST(self, root: TreeNode) - TreeNode: self.total 0 def dfs(node): if not node: return dfs(node.right) self.total node.val node.val self.total dfs(node.left) dfs(root) return root这段代码的核心就三行先递归右子树然后累加并赋值最后递归左子树。self.total的作用就是那个贯穿始终的“身高总和”。注意一个很多人踩过的坑self.total 0必须放在convertBST方法内部不能在类属性里直接初始化total 0。因为 LeetCode 的判题系统会复用同一个 Solution 实例跑多个测试用例如果total是类属性第二个用例开始时会带着上一个树累加出来的脏值导致结果全部偏大。正确的做法就是每次调用convertBST时把total重置为 0。如果实在不放心也可以在dfs内部用nonlocal total声明一个嵌套函数内的局部变量效果等价class Solution: def convertBST(self, root: TreeNode) - TreeNode: total 0 def dfs(node): nonlocal total if not node: return dfs(node.right) total node.val node.val total dfs(node.left) dfs(root) return root两种写法的思路完全一样选自己顺手的即可。3.2 函数式写法把累加和塞进返回值里如果你不喜欢全局变量或者面试官要求写一个“无外部状态”的函数可以用返回值传递累加和。思路是递归函数接收一个“已经累加好的值”处理完当前子树后把更新后的累加和原样返回给上一层。class Solution: def convertBST(self, root: TreeNode) - TreeNode: def dfs(node, acc): if not node: return acc acc dfs(node.right, acc) acc node.val node.val acc return dfs(node.left, acc) dfs(root, 0) return root这个写法初看有点绕我拆开解释。dfs(node, acc)表示“从当前节点这一层开始初始累加值是 acc遍历完 node 以及 node 的所有左子树节点之后返回最新的累加值”。以节点 4、右子树 6、左子树 2 的树为例调用dfs(4, 0)先处理右子树dfs(6, 0)返回 6acc变成 6加上 4 变成 10赋值给根节点再处理左子树dfs(2, 10)返回 12最终返回 12。注意最后一行return dfs(node.left, acc)是整个函数最容易写错的地方。有些人会写成dfs(node.left, acc) return acc这样dfs调用确实执行了但左子树里更新过的累加值没有被传出去不影响这道题的最终结果因为根节点的值是赋完的但逻辑上就不完整了。尤其是把这段代码改成“计算每个节点的排名”之类需要后续累加值的题目时漏掉返回值会直接出 bug。所以函数式写法要记住一件事左子树的返回值必须继续向外返回。3.3 时间复杂度和空间复杂度是怎么算出来的不管用全局变量还是函数式写法每个节点都只会被访问一次每次访问只做常数次操作所以时间复杂度是 O(n)n 是树的节点数。空间复杂度的关键不在显式数据结构而在于递归调用栈。递归深度取决于树的高度在平衡二叉树上是 O(log n)在退化成链表的极端 BST 上是 O(n)。LeetCode 的测试用例一般不会把链状树压到栈溢出但如果面试官追问最坏情况你得能说出来空间复杂度是 O(h)h 是树高最坏 O(n)平均 O(log n)。这一点也自然引出了下一章的问题能不能把空间复杂度压到 O(1)能用莫里斯遍历。4. 从递归到迭代显式栈和莫里斯遍历的空间优化路线4.1 用显式栈复刻“右根左”顺序递归虽然好写但本质上是依赖系统栈不想用递归的时候可以用显式栈来模拟class Solution: def convertBST(self, root: TreeNode) - TreeNode: total 0 node root stack [] while stack or node: while node: stack.append(node) node node.right # 先一路向右 node stack.pop() total node.val node.val total node node.left # 转向左子树 return root这个套路和中序遍历的迭代写法几乎一模一样只是把“一路向左”换成“一路向右”把弹栈后的处理顺序反过来。你如果写过中序遍历的迭代版本这题就是在它基础上改两个方向的镜像操作。为什么这样写能得到降序因为正向中序遍历是“左根右”最左侧节点最先访问现在改成“右根左”最右侧节点最先访问。迭代的本质就是把递归调用栈里的“压栈-处理-弹栈”流程显式化。每一轮内层 while 把所有右孩子压进栈弹出来的就是当前子树中值最大的节点赋值完成后转向它的左子树继续找次大的节点。4.2 莫里斯反向中序遍历把线索藏在空指针里莫里斯遍历是二叉树遍历中比较高级的技巧核心思想是利用节点中没有被使用的空指针右指针或者左指针临时记录中序遍历的后继或者前驱位置实现不用栈、不用递归的 O(1) 空间遍历。标准的莫里斯遍历针对中序遍历这里给出对应的反向版本。先说结论反向莫里斯遍历的关键是在每个有右子树的节点上找到它右子树的最左节点把这个最左节点的左指针临时指向当前节点。这样等右子树处理完后可以借助这条“线索”直接跳回当前节点。class Solution: def convertBST(self, root: TreeNode) - TreeNode: total 0 cur root while cur: if cur.right: succ cur.right while succ.left and succ.left is not cur: succ succ.left if succ.left is None: succ.left cur cur cur.right continue else: succ.left None total cur.val cur.val total cur cur.left return root这段代码初看很难懂我建议你拿一棵小树在纸上逐步画一遍。以最简单的 4-2-6 树为例cur指向 4有右子树 66 的左指针为空所以把 6 的左指针指向 4cur移到 6cur指向 6没有右子树访问 6赋值后cur通过左线索跳到 4cur指向 4右子树还是 6但此时 6 的左指针已经指向 4说明右子树处理完了所以拆除线索把 6 的左指针置空访问 4然后cur移到左子树 2cur指向 2没有右子树访问 2。访问顺序正好是 6、4、2。线索建立时临时改变了树结构但访问完成后会恢复原状转换后得到的仍然是一棵合法 BST。莫里斯遍历写起来容易在“找后继”和“拆线索”之间绕晕我的建议是不要把它当作首选的笔试方案但面试时能口述思路、并能指出它把空间复杂度降到 O(1)已经是很好的加分表现。实际工程里几乎不会为了省 O(h) 的栈空间而引入这么复杂的指针操作它的价值更多是在算法训练和面试展示层面。4.3 三种实现的取舍实现方式时间复杂度空间复杂度代码量容易出错的地方递归 全局变量O(n)O(h)少全局变量状态残留递归 返回值O(n)O(h)中返回值漏传迭代 显式栈O(n)O(h)中入栈方向写反莫里斯反向遍历O(n)O(1)多线索建立/拆除混乱如果你是在笔试环境时间有限优先写递归如果你在准备面试且希望展示自己对遍历理解的深度可以提一句“还有莫里斯遍历能把空间压到 O(1)”并简单说明线索怎么建立。不要在面试现场憋莫里斯写 10 分钟性价比不高。5. 实战踩坑这道题最容易翻车的几个细节5.1 “大于等于”不等于“大于”重复值节点最容易出错LeetCode 这题的测试用例里节点值不重复但二叉搜索树在实际场景中完全可以包含重复值比如把小于等于放左子树或者大于等于放右子树。如果面试官追问重复值怎么办你要能立刻反应过来累加树要求“所有不小于当前节点值的节点值之和”所以重复值的节点也要把彼此加进去。举个例子一棵树有两个值都为 5 的节点其中一个是另一个的祖先。转换时第一个 5 累加后第二个 5 也要把第一个 5 的新值算进去所以结果中两个 5 的新值相同都等于原树所有大于等于 5 的节点和。如果你的代码写的是“只累加严格大于当前节点的值”结果就会偏小而且只有恰好有重复值时才出错非常隐蔽。我建议你写代码时把注释写清楚“当前累加和包含已经访问过的所有节点包括值相同的节点”避免自己都想不起来当初为什么要这么写。5.2 值传递还是引用传递累加和传进递归后“消失”了这是新手最容易踩的一个坑。Python 里整数是不可变对象函数参数传递相当于传了一个引用的副本函数内部重新赋值不会影响外部变量。看这段错误代码class Solution: def convertBST(self, root: TreeNode) - TreeNode: def dfs(node, total): if not node: return dfs(node.right, total) total node.val node.val total dfs(node.left, total) dfs(root, 0) return root表面上看total在递归里加了值但每层递归里的total node.val都会生成一个新的整数对象赋给局部变量total并不会改到上一层传入的那个total。所以右子树里累加的结果传不回根节点根节点的新值只等于自己的原值加 0。这就是我前面强调“要么用全局变量要么用返回值”的根本原因。在 Java、C 这类语言里也有类似问题Java 的int是值传递传进去改完不返回外部同样看不到C 可以传int引用或者封装成一个struct。牢牢记住一句话累加和是所有递归层共享的状态不能用普通值语义传递。5.3 测试用例别只盯着示例用中序数组自检写完代码之后最稳的验证方式不是只看示例输出而是写一个辅助函数对转换后的树做中序遍历检查结果是否是非递减序列。因为累加树本质上还是一棵二叉搜索树转换只是把值变大了BST 结构没变所以中序遍历结果必须保持升序。更进一步的验证办法是先拿到原树的中序数组然后从后往前做后缀和把后缀和数组与转换后树的中序数组逐位比较。这样做的好处是你能把“树上的逻辑”降维到“数组上的逻辑”出错时定位更快。如果懒得写完整验证函数至少检查两点最大值节点的新值等于原值最小值节点的新值等于整棵树所有节点之和。这两个边界点能拦住很大一部分 bug。5.4 LeetCode 判题环境中的对象复用问题前面提到过self.total要在convertBST内部初始化这里再展开讲一下。LeetCode 的后端会创建多个测试用例但是同一个 Solution 类的实例可能被复用。如果你写成class Solution: total 0 def convertBST(self, root: TreeNode) - TreeNode: ...那么第一个用例跑完后total停留在 36第二个用例开始时total不是 0 而是 36所有节点的新值都会偏大 36。这个问题在本地跑单个用例时完全复现不出来只有提交到平台上跑多个用例才会暴露。解决办法就是每次方法调用开始时手动重置。这也是为什么我推荐把状态放在方法内部、嵌套函数外部而不是放在类属性上的原因——状态的作用域越短越不容易被污染。6. 做完 538 之后一个题的结束一类题的开始6.1 反向出题“小于等于当前节点值的和”怎么改如果面试官反过来问你把二叉搜索树每个节点改成“所有小于等于它的节点值之和”你会不会改答案特别简单把遍历顺序从“右根左”改成“左根右”也就是正常的升序中序遍历。累加变量还是那个累加变量只是现在它累计的是所有已经访问过的、比当前节点小的节点值。class Solution: def convertBST(self, root: TreeNode) - TreeNode: self.total 0 def dfs(node): if not node: return dfs(node.left) self.total node.val node.val self.total dfs(node.right) dfs(root) return root对比一下 538 的代码唯一的区别就是先递归左还是先递归右。这说明这类题的本质就是“你选一条遍历方向累加变量跟着走”方向选对了代码几乎不用思考。6.2 二叉搜索树经典题的共同套路把 538 做完后再看其他 BST 题会发现很多都是中序遍历或反向遍历的变体题目考点解题关键230. 二叉搜索树中第K小的元素中序遍历计数升序中序第 K 个节点98. 验证二叉搜索树中序遍历单调性比较前后节点值是否严格递增114. 二叉树展开为链表遍历顺序与指针修改前序或中序记录前驱节点1038. 从二叉搜索树到更大和树反向中序累加与 538 完全相同看到没有BST 的很多题都在考一个核心能力能不能根据题目要求确定遍历顺序然后在这个顺序上维护一个流动变量。538 的累加变量是“和”230 的流动变量是“计数”98 的流动变量是“上一个节点的值”114 的流动变量是“链表的末尾节点”。框架一样变量含义不一样而已。6.3 如果这不是一棵二叉搜索树呢一个值得思考的延伸问题如果输入是一棵普通二叉树没有“左小右大”的约束题目还能这么做吗显然不能因为你没有任何遍历顺序能保证“先访问到所有大于当前节点的节点”。暴力解法是先遍历一次收集所有节点值排序然后对每个节点用二分查找或者哈希表计算后缀和再更新到节点上时间复杂度升到 O(n log n)。这个对比反过来印证了 BST 结构给算法带来的巨大简化。做算法题有一个很朴素的经验题目的数据结构越特殊越要优先利用它的特殊性质。二叉搜索树的特殊性质就是有序性任何和大小比较、前缀和、后缀和、排名相关的操作都应该第一时间联想到中序遍历以及它的镜像。我个人在实际刷题中的体会是这类“原地改值”的题目特别适合锻炼对树形结构和遍历顺序的理解。你写不出代码没关系先尝试在纸上手动走一遍小例子找到累加变量流动的规律再用代码表达出来基本就是正确的实现。最后一招如果你担心莫里斯遍历拆线索时把树弄坏写完以后顺手把树还原成中序数组打印一遍非递减就说明操作对了。这个验证习惯帮我抓住了不少自以为正确的小错误。