题目描述
思路解析动画文字版
记住这套「右根左降序、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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题