题目描述
思路解析
一句话答案：LeetCode 1038 从二叉搜索树到更大和树：把每个节点改成树里所有不小于它的值之和；BST 反中序天然从大到小，用累加器边加边回填一趟就成，时间 O(n)、空间 O(h)。
每个节点要变成哪些值的和
给一棵二叉搜索树，也就是左小右大的那种树 root，要求把每个节点的值改成整棵树里所有大于或等于它的节点值之和，它自己也算一份。题面例子 root=[50,30,70,20,40,60,80]，改完是 [260,330,150,350,300,210,80]：最大的 80 头顶没有更大的，还是 80；根 50 上面压着 80、70、60 再加它自己，滚成了 260。
对每个节点都扫一遍全树，慢在哪
一个节点要知道有多少值不小于自己，最直白的办法是拿它和其余每个节点比一遍，把够大的加起来。可这样每个节点都得走一趟全树，n 个节点就是 n 乘 n，O(n²)，上万个节点就扛不住。退一步，把所有值收集起来排好序、再求后缀和也能算，但排序本身要 O(n log n)，而且白白丢掉了 BST 早就排好的顺序。
BST 反着走，正好是从大到小
BST 有个现成的性质：中序遍历，也就是按左、根、右的顺序走，吐出来的值是升序的。把这个顺序整个反过来，右、根、左，走出来就是降序，从最大的节点开始一路变小。这条反中序的路恰好对上题目要的「比它大的先算」：轮到某个节点时，所有比它大的值都已经走过了。
一个累加器边走边加、边回填
备一个累加器 s，起始为 0，全程只增不清零。递归按反中序走：先钻进右子树 dfs(root.right)，把更大的那些先处理完；回到当前节点做两件事，s 先加上它的原值，再把它的值改写成现在的 s；最后钻进左子树 dfs(root.left)。轮到某节点时，s 里装的正是所有比它大的值之和，加上它自己这一份，回填的就是它该有的更大和。两步不能倒：先加进 s 再回填，s 里才含它自己那份。
拿题面这棵树，从 80 倒着填到 20
反中序的访问顺序是 80、70、60、50、40、30、20，s 从 0 起：到 80，s=0+80=80，80 回填还是 80；到 70，s=80+70=150，70 变 150；到 60，s=150+60=210，60 变 210；到 50，s=210+50=260，50 变 260；到 40，s=260+40=300，40 变 300；到 30，s=300+30=330，30 变 330；到 20，s=330+20=350，20 变 350。倒着填一圈，把这些值按原位摆回去，[260,330,150,350,300,210,80] 正是题面的答案。
走反了中序、或中途把 sum 清零，回填就全错
每个节点只被访问一次，一次加法配一次赋值，时间 O(n)；额外开销是递归栈，深度等于树高 h，平衡时约 O(log n)，退化成一条链时到 O(n)。只有一个节点时，s 加上它自己、回填仍是原值；整棵树往右斜成一条链时，反中序就是从最右最大的那个节点起倒着走。
方向、清零、顺序，走反哪个答案都会崩。方向写成普通中序从小到大走，轮到某节点时比它大的还没进 s，回填必然偏小。s 中途清零，前面攒的更大值全丢，剩下的节点只累到自己往后那一截。加和回填的顺序一颠倒，先回填再加就是拿旧 s 盖掉原值，它自己那份反倒少算。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「右根左降序、sum 先加原值、再把 sum 回填」，下面每帧都在套它。
准备 · 反中序从最大值起：这是一棵二叉搜索树，右边的值都比左边大。我们要按从大到小的顺序访问，所以反中序：先右、再根、最后左。从根 50 出发，先一路往右下扎，去找整棵树最大的那个节点。
下探 · 50 先走右孩子 70：还轮不到 50，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 70，那边的值都比 50 大。
下探 · 70 先走右孩子 80：还轮不到 70，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 80，那边的值都比 70 大。
访问 · 轮到 80，sum 加上它：80 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 80 加进累加和：0 加 80 等于 80。此刻 sum 里装的，就是所有不小于 80 的节点值之和。
回填 · 80 改写成 80：80 是整棵树最大的值，没有比它更大的节点，sum 就等于它自己，回填后还是 80。
访问 · 轮到 70，sum 加上它：70 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 70 加进累加和：80 加 70 等于 150。此刻 sum 里装的，就是所有不小于 70 的节点值之和。
回填 · 70 改写成 150：把当前节点的值改写成 sum，也就是从 70 变成 150。比 70 大的节点早就加进 sum 了，所以这个 150 正是它该有的更大和。
下探 · 70 再走左孩子 60：70 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 60，它比 70 小。注意 sum 不清零，继续往下累加。
访问 · 轮到 60，sum 加上它：60 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 60 加进累加和：150 加 60 等于 210。此刻 sum 里装的，就是所有不小于 60 的节点值之和。
回填 · 60 改写成 210：把当前节点的值改写成 sum，也就是从 60 变成 210。比 60 大的节点早就加进 sum 了，所以这个 210 正是它该有的更大和。
访问 · 轮到 50，sum 加上它：50 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 50 加进累加和：210 加 50 等于 260。此刻 sum 里装的，就是所有不小于 50 的节点值之和。
回填 · 50 改写成 260：把当前节点的值改写成 sum，也就是从 50 变成 260。比 50 大的节点早就加进 sum 了，所以这个 260 正是它该有的更大和。
下探 · 50 再走左孩子 30：50 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 30，它比 50 小。注意 sum 不清零，继续往下累加。
下探 · 30 先走右孩子 40：还轮不到 30，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 40，那边的值都比 30 大。
访问 · 轮到 40，sum 加上它：40 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 40 加进累加和：260 加 40 等于 300。此刻 sum 里装的，就是所有不小于 40 的节点值之和。
回填 · 40 改写成 300：把当前节点的值改写成 sum，也就是从 40 变成 300。比 40 大的节点早就加进 sum 了，所以这个 300 正是它该有的更大和。
访问 · 轮到 30，sum 加上它：30 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 30 加进累加和：300 加 30 等于 330。此刻 sum 里装的，就是所有不小于 30 的节点值之和。
回填 · 30 改写成 330：把当前节点的值改写成 sum，也就是从 30 变成 330。比 30 大的节点早就加进 sum 了，所以这个 330 正是它该有的更大和。
下探 · 30 再走左孩子 20：30 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 20，它比 30 小。注意 sum 不清零，继续往下累加。
访问 · 轮到 20，sum 加上它：20 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 20 加进累加和：330 加 20 等于 350。此刻 sum 里装的，就是所有不小于 20 的节点值之和。
回填 · 20 改写成 350：把当前节点的值改写成 sum，也就是从 20 变成 350。比 20 大的节点早就加进 sum 了，所以这个 350 正是它该有的更大和。
完成 · 整棵树已变成更大和树：反中序访问顺序是 80、70、60、50、40、30、20，sum 一路累加成 80、150、210、260、300、330、350，依次回填到各节点。最大的 80 还是 80，最小的 20 收齐了所有节点变成 350。一遍 DFS 就把整棵树改成了更大和树。
边界先想清：单节点直接加自身；右单链时反中序就是先访问最右最大的那个。
面试重点：和 538 同题、非 BST 要另想办法、以及迭代或 Morris 的空间优化。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(root: Optional[TreeNode]): if root is None: return dfs(root.right) nonlocal s s += root.val root.val = s dfs(root.left) s = 0 dfs(root) return root复杂度
- 时间：O(n)，反中序遍历每个节点恰好访问一次，每次只做一次加法和一次赋值
- 空间：O(h)，递归栈深 = 树高 h；平衡时约 O(log n)，最坏退化成链时 O(n)
易错点
面试追问把动画讲成自己的话
追问这题和 538「把二叉搜索树转换为累加树」是不是一样？
追问如果不是 BST，是普通二叉树呢？
追问能不能不用递归、把空间压到 O(1)？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
根到叶路径上的不足节点
LeetCode 1080 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题