“把二叉树转换为累加树”这八个字曾经让我在LeetCode 538这道题上白交了两次错误答案。为什么因为题名里藏着最关键的信息但很多人第一眼只看到“二叉树”和“累加”却漏掉了原题完整表述里的“二叉搜索树”。没错LeetCode 538的完整名称是把二叉搜索树转换为累加树Convert BST to Greater Tree少了“搜索”两个字题目性质就完全变了。这道题算是树遍历入门必做题既考二叉搜索树的性质又考中序遍历的变体还能一路从递归写到迭代再写到Morris几乎可以借一道题吃透一整类问题。这篇文章我会从一个刷题者的角度把前置知识、三种解法、踩坑经验以及它背后延展出来的套路全部讲清楚适合正在刷LeetCode、准备面试或者单纯想搞懂“为什么要这样遍历”的朋友。1. 先认出前提为什么题干里“二叉搜索树”五个字不能省1.1 累加树只在有序结构里才有意义先看题目定义给定一颗二叉搜索树BST把每个节点的值替换成“原树中所有大于等于该节点值的节点值之和”。举个例子一颗包含值1到7的BST转换后每个节点的值都会变大而且原值越小的节点新值越大。这里有个很容易被忽略的点这个定义只在BST里成立。如果换成一颗随机二叉树问题会立刻变成一个没有办法高效求解的怪物。原因很简单随机二叉树没有全局顺序大于等于某个节点值的其他节点可能散布在左子树、右子树、甚至隔了好几层的地方你在一次遍历里根本不知道“谁比当前节点大”。举一个极端例子根节点值是1左子树某个节点的值是100右子树某个节点的值是2那么根节点的新值必须把整棵树都加进去可是按照普通二叉树的前序、中序、后序没有任何一种遍历顺序能保证“一路遇到的所有节点恰好都是递增或递减的”。这就是第一步的关键观察题目里真正起作用的是BST不是二叉树。BST的核心性质是左子树所有节点值小于根节点右子树所有节点值大于根节点并且中序遍历左根右能得到一个严格递增序列。有了这个序列原本散落在树里的节点就变成了一条有序数组累加树这个定义才有地方落脚。我在面试和刷题社区里见过不少同学上来就写一个通用的“树”函数然后把LeetCode 538的原题发到讨论区问为什么错。其实只需要多读一遍题把“二叉搜索树”圈出来思路就已经完成了百分之三十。刷题的第一条铁律永远是先识别题目给了什么特殊结构再决定用什么算法。1.2 把累加过程翻译成我们更熟悉的“后缀和”假设现在手里有一颗BST中序遍历结果是[1, 2, 3, 4, 5, 6, 7]。题目要求每个节点变成“原树中所有大于等于它的节点值之和”放到数组语境下就是每个位置的新值等于从它自己到数组末尾所有元素的和。值77 6 5 4 3 2 1 28值66 5 4 3 2 1 21等等这里要注意计算方向。严格来说中序数组是[1,2,3,4,5,6,7]原树中“大于等于某个值”的所有节点在数组里对应的是从该位置到末尾的一段所以这是标准的后缀和1 对应 1 2 3 4 5 6 7 282 对应 2 3 4 5 6 7 273 对应 3 4 5 6 7 254 对应 4 5 6 7 225 对应 5 6 7 186 对应 6 7 137 对应 7这个转换非常关键。一旦你把一颗BST摊平成有序数组“把BST转换为累加树”就等价于“把数组中每个元素替换为后缀和”。而数组后缀和的求法很简单从右往左扫一遍维护一个累加变量cnt遇到数组元素就加上、然后更新当前位置。那问题来了我们能不能不把树变成数组直接在树上完成这个“从右往左扫一遍”的操作答案是可以靠的正是反向中序遍历也就是右-根-左。中序遍历是升序右-根-左就是降序。降序遍历BST相当于从数组末尾往开头走正好能满足后缀和的计算顺序。于是解法就非常清晰了用递归或者栈实现右-根-左遍历一路累加并更新节点值。1.3 面试时先把这个观察说出来比直接写代码加分这里想多说一句面试技巧。很多同学看到这个题就开始默写代码其实面试官往往想先听你描述思路。如果你能立刻说出“BST中序是升序题目本质是把中序序列替换成后缀和所以用反向中序遍历”面试官就知道你对二叉树遍历是真的理解到位了而不是背了两三道题模板。这个“先想清楚再动手”的习惯在后面的迭代写法和Morris写法里也会反复用到。2. 先想通“后缀和数组”再动手写递归2.1 两趟遍历最直观的保底方案如果你在考场上一下子没想通反向中序遍历还有一个不太优雅但绝对正确的保底方案先中序遍历收集数组再计算后缀和最后二次遍历树替换值。我把这个方案称为“扫描两趟”它最大的价值是帮你验证自己对题目的理解对不对。class Solution: def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: vals [] # 第一趟中序遍历收集节点值 def inorder(node): if not node: return inorder(node.left) vals.append(node.val) inorder(node.right) inorder(root) # 计算后缀和用字典记录每个原值应替换成什么 total 0 suffix_map {} for v in reversed(vals): total v suffix_map[v] total # 第二趟再遍历一次树替换节点值 def update(node): if not node: return update(node.left) node.val suffix_map[node.val] update(node.right) update(root) return root两趟遍历的缺点是显而易见的需要用额外的数组和哈希表空间复杂度达到O(n)并且树要遍历两次理论上慢一些。但在你刚开始接触这道题时这个写法能帮你建立“中序序列和树结构之间的对应关系”非常值得亲自写一遍。我见过不少同学第一遍直接写反向中序遍历写错了方向却看不出来就是因为脑子里没有一个“数组化”的参照物。把两趟遍历写出正确答案再去优化成单趟是最稳的学习路径。2.2 反序中序遍历真正推荐的单趟标准解法接着说最优写法只用一次右-根-左遍历边遍历边累加。维护一个累计变量total从最大节点开始处理每访问到一个节点说明它右子树的所有节点也就是所有比它大的节点都已经处理完毕了此时total里保存的就是“所有比当前节点大的节点的值之和”把当前节点的原值加到total上再把当前节点值更新为total。一句话概括total root.val; root.val total顺序是先加再替换。正因为我们是降序访问每次取到的节点值都等于“原树中当前节点以及所有比它大的节点值之和”正好满足后缀和的定义。class Solution: def __init__(self): self.total 0 def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: 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这段代码大概就是LeetCode 538最经典、最简洁的解法。递归结构非常清晰你甚至不需要在脑子模拟每一步只需要记住“右根左降序边加边替换”整个算法就立住了。2.3 为什么更新节点值不会“污染”后面的累加这里有一个新手容易犯怵的细节我改了node.val万一后面累加时加到的不是原值而是新值会不会算错答案是不会而且这个巧合背后有严格的遍历顺序保证。关键点在于当你处理某个节点时这个节点是当前未处理节点里的最大值。右子树已经处理完左子树还没处理。累加total时使用的是node.val此刻读取到的仍然是该节点在原始树里的值因为它还没有被写入新值。左侧子树的节点都比它小它们的新值应该包含“当前节点的原值”所以total里的累计信息不会因为节点值被覆盖而丢失。换句话说节点值更新发生在累加之后而遍历方向又是从大到小所以每一步读到的一定是干净的原值。我用一个具体BST走一遍大家就彻底明白了。考虑中序为[1,2,3,4,5,6,7]的BST反序访问顺序是7,6,5,4,3,2,1遍历序号访问节点原值total累加前total累加后节点最终值1707726713133513181844182222532225256225272771272828最终树上所有节点值变为[28,27,25,22,18,13,7]。这个表我建议你亲手在纸上画一遍尤其是把树的形状比如根是4左子树是2和6那层画出来跟着箭头标一遍total的变化对理解递归顺序极有帮助。3. 递归解法最容易翻车的三个细节和一次完整手推3.1 细节一累计变量到底放哪决定你AC还是报错上面代码里我把total放成了类属性self.total这是Python里比较省事的做法。除此之外还有其他写法但每种写法的坑不一样这里列出来对比一下。第一种嵌套函数配合nonlocal total。class Solution: def convertBST(self, root: Optional[TreeNode]) - Optional[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第二种用一个list包一层当“可修改的盒子”。class Solution: def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: total [0] def dfs(node): if not node: return dfs(node.right) total[0] node.val node.val total[0] dfs(node.left) dfs(root) return root第三种C里直接传引用Java里用类成员变量。class Solution { private int total 0; public TreeNode convertBST(TreeNode root) { dfs(root); return root; } private void dfs(TreeNode node) { if (node null) return; dfs(node.right); total node.val; node.val total; dfs(node.left); } }Python最容易踩的坑是在嵌套函数里直接写total node.val而不加nonlocal total运行时会抛UnboundLocalError。原因很简单Python看到total在函数内部被赋值就会把它当成局部变量而局部变量在使用前没有初始化。这是Python闭包的老大难问题几乎每个写递归的人都栽过一次。所以我的习惯是如果递归嵌套层数不多直接用类属性或者nonlocal如果代码要给别人看尽量写类属性理由是肉眼更不容易出错。3.2 细节二为什么“写着写着就报运行时错误”再来说一个很应景的热搜词写二叉树程序时为什么总是报运行时错误。我总结下来多半是三个原因这个题里全都可能触发。第一个是空指针。很多人递归开头没写if not node: return或者在空树上调node.val直接访问None的属性。这在LeetCode上报的是AttributeError: NoneType object has no attribute val。二叉树题第一件事永远是处理空节点这几乎已经成了肌肉记忆。第二个是递归深度爆栈。二叉搜索树在极端情况下会退化成一条链表比如节点值1到10000依次插入树的深度就是10000。Python默认递归深度是1000一旦超过就抛RecursionError。LeetCode的深测用例虽然不一定这么极端但我在本地测试时经常遇到。这时候你可以临时提高递归上限import sys sys.setrecursionlimit(20000)不过更稳妥的做法是改用显式栈的迭代写法毕竟面试官也可能会追问“如果树很深递归还适用吗”这也是我下一章要展开讲的内容。第三个是返回类型不一致。比如你的dfs函数在某个分支里写了return dfs(node.right)在另一个分支里没有返回值最后导致上一级调用拿到None参与计算。在538这道题里我们其实不需要用递归的返回值直接原地修改树就够了。但如果写成有返回值的风格最好保持一致不要混用。3.3 细节三用例子手推一遍胜过看十遍题解写这道题之前我强烈建议你拿出纸笔把前面那个[1,2,3,4,5,6,7]的例子按“右根左”的顺序走一遍。你会发现递归的调用顺序本质上就是一棵树的“先右后左”DFS而total从7一直累加到28的过程跟数组后缀和的计算顺序完全一致。手推时注意看每次递归进入一个节点的右孩子之前total等于多少回来之后total变成多少当前节点能拿到的total是不是正好是“所有比它大的和”。这个模拟过程我做了不止一次每一次都能发现对遍历顺序理解的偏差。比如我第一遍写的时候不小心写成了“左根右”导致节点被替换成前缀和结果整棵树的值全错了。事后用数组一对照才发现左根右是前缀和只有右根左才是后缀和一句话点醒了自己。4. 显式栈和Morris遍历空间复杂度进阶之路4.1 用显式栈模拟“右-根-左”递归版代码简洁但深度过大时会爆栈而且面试官经常追问“能不能用迭代实现”。这时候我们需要用显式栈模拟系统递归栈写法和标准中序遍历的迭代版完全对称只是先压右子树再压左子树。直接给代码class Solution: def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: total 0 stack [] cur root while stack or cur: # 一路向右把所有右子节点入栈 while cur: stack.append(cur) cur cur.right # 弹出当前最大的未处理节点 cur stack.pop() total cur.val cur.val total # 处理完当前节点后转向左子树 cur cur.left return root这段代码的循环不变量是栈里保存的是从根开始的“右链”上的节点弹出的顺序恰好是节点的降序。我建议你干一件事把递归版和迭代版并排放在一起对照着看dfs(node.right)对应的是内层while往栈里压右孩子node.val total对应的是弹出栈顶后的三段操作dfs(node.left)对应的是cur cur.left。这样一来迭代版只是把系统的调用栈换成了显式栈逻辑上没有增加任何新东西。4.2 Morris遍历把空间复杂度压到O(1)迭代版解决了递归深度问题但空间复杂度还是O(h)h是树高。面试官如果继续追问“能不能不用任何栈和额外空间”这就到了Morris遍历的舞台。Morris的核心思想是借助BST叶子节点上的空指针临时制造线索遍历完再恢复从而做到不需要栈也能在遍历完右子树后回到当前节点。反向Morris的逻辑可以这样理解我们希望按右-根-左的顺序遍历所以在进入右子树前先找到这棵右子树里“在遍历顺序上最先被访问的节点”也就是从右孩子开始一路向左走到最深的那个节点记为succ。把succ的左指针临时指向当前节点cur相当于留了一个“回头路”。当cur从右子树一路走下去最终必然能通过succ.left这条线索回到cur。这时说明cur的右子树已经全部处理完毕该处理cur本身了处理完后恢复succ.left为None再往左走。代码逐行解释一遍class Solution: def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]: total 0 cur root while cur: if cur.right is None: # 没有右子树直接处理当前节点然后向左 total cur.val cur.val total cur cur.left else: # 找到右子树中最左侧的节点succ 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 else: # 第二次经过说明右子树已经处理完恢复线索 succ.left None total cur.val cur.val total cur cur.left return root用前面那颗树简单手推一遍关键节点cur4时右子树最左节点是5建立5-4的线索然后cur转到6一路处理7、6、5最后通过5.left回到4这时右子树全部处理完处理4并恢复线索再转向2。整个过程中额外空间只有一个total和几个指针变量空间复杂度是O(1)。值不值得为了O(1)空间写这么绕的代码从工程角度讲不值得实际项目中没人会为了省空间用Morris改树结构因为出错概率太高但从算法学习角度讲Morris遍历让你真正理解了“栈到底在代替我们记住什么”以及“线索二叉树”这个概念是怎么被发明出来的。4.3 线索二叉树和Morris的关系“线索二叉树”听起来像另一个考点其实它和Morris遍历是同一枚硬币的两面。线索二叉树的定义是把二叉树中空闲的指针利用起来让左指针指向遍历序列的前驱、右指针指向遍历序列的后继从而不需要递归和栈就能直接线性地遍历整棵树。Morris遍历正是这个思想的临时版本它不改变树的最终形态而是在遍历过程中借用空闲指针做“临时线索”用完之后立刻撤销。理解这层关系对做树相关的算法题非常有帮助。比如你以后看到某些要求O(1)空间的遍历题第一反应就应该是Morris思路而考试题目里如果明确允许修改树的结构也可以直接采用线索二叉树的路数。538这道题是练习Morris的最佳载体因为它不仅涉及反向Morris而且代码短。我建议你有余力时把Morris版抄三遍抄到能默写为止这玩意在面试里写出来通常能让面试官眼前一亮因为多数候选人连显式栈迭代版都未必能一次写对。下面把三种写法的优劣放在一起对比写法时间复杂度空间复杂度代码可读性适合场景递归O(n)O(h) 递归栈高最简洁面试默认首选显式栈O(n)O(h) 显式栈中树较深避免爆栈MorrisO(n)O(1)低容易写错面试追问空间优化时间复杂度都是O(n)遍历一遍树每节点访问常数次不需要区分。空间上递归和迭代都是树高h只有Morris真正做到了常数空间。工程上推荐递归深度风险场景用显式栈Morris用来拔高理解。5. 从538长出来的类型题反向中序遍历一鱼多吃5.1 一套模板吃透“第K大”“累加”“反向DFS”538这道题最大的价值不在于它本身有多难而在于它把“反向中序遍历”这个套路展示得非常标准。只要你掌握了“右-根-左 维护一个外部状态变量”这个组合下面这些题会变得毫无压力。剑指Offer 54二叉搜索树的第k大节点。解法就是反向中序遍历数到第k个节点时返回和538几乎一模一样只是把total node.val; node.val total换成了k--; 判断是否等于0。LeetCode 230二叉搜索树中第K小的元素。这个是“左-根-右”正向中序遍历计数属于同一个模板的镜像版本。LeetCode 1038从二叉搜索树到更大和树。这题和538是完全同构的问题只是表述方式不同解法可以直接复用。我把这套模板抽象成三个步骤判断题目要求的是正序处理还是倒序处理。凡是“大于当前节点的和”“第k大”“从大到小累加”基本都是反向中序遍历决定遍历顺序右-根-左对应倒序左-根-右对应正序确定维护的状态变量累加题是total计数第k题是计数器求和题可能是路径和。5.2 什么时候用递归、栈、还是Morris很多人拿到这类题会纠结该用哪种写法。我的判断标准依次是这样如果面试没有额外限制第一选择永远是递归。因为它最接近算法思想本身代码量最小面试官看你的思路最清楚。但前提是你平时写好递归的边界条件别一棵链状树就把栈打爆。如果题目明确说树很大、或者递归深度可能超过限制那就换显式栈。显式栈的代码不难只要把递归函数的执行顺序对应到while循环里就行。面试时主动写迭代版也能展示你对递归背后调用栈的理解。如果面试官追问道“能不能做到O(1)空间”这时候才写Morris。但老实说我自己写Morris在面试中成功默写的次数屈指可数平时必须练到肌肉记忆。在真实的项目代码里我基本不会对一棵树用Morris因为临时线索会改变树结构一旦恢复失败就是埋雷但它作为算法思维题确实能拉开候选人的差距。5.3 我刷这道题的真实体会最后说点个人经验。我最初做这个题时犯了三个错第一个是没看清“二叉搜索树”这个前提拿普通二叉树硬套第二个是写反了遍历方向把右根左写成了左根右结果得到的是前缀和而不是后缀和第三个是total变量作用域写错在Python里栽了UnboundLocalError的跟头。这三个错误每一个都能靠“先在纸上写出中序数组然后自己算一遍后缀和”来避免。所以我的最后建议是别急着把题解代码敲进编辑器先用手写一遍中序数组和后缀和再对照树结构写出访问顺序。这一步花不了五分钟但能让你真正理解538的每一个细节。等你刷到LeetCode热门100题、或者准备周赛时遇到类似的树上累加题你会感谢当初这个“笨办法”打下的底子。LeetCode 538这道题我前前后后在不同阶段做了四遍每一遍都有新收获。第一遍是学递归第二遍是学迭代第三遍是折腾Morris第四遍是把它掰开揉碎讲给别人听。二叉树的遍历看起来是基础中的基础但能把“为什么用右根左”和“为什么节点值不会被污染”讲清楚才算是真正吃透了它。这也正是我为什么一直跟人强调刷题不是背答案是练思维。希望这篇文章能成为你攻克这题、乃至整个BST系列的起点。