LeetCode 1038中等树 · BST

从二叉搜索树到更大和树图解题解

这道题到底在问什么

给定二叉搜索树 root，把每个节点的值改成树中所有大于或等于该节点值的节点值之和（含它自己），返回改完的树。提示：BST 节点值互不相同，中序（左、根、右）是升序。

输入: root=[50,30,70,20,40,60,80]
输出: [260,330,150,350,300,210,80]

最优解：一步一步想明白

3记住这套「右根左降序、sum 先加原值、再把 sum 回填」，下面每帧都在套它。
4从根 50 先扎向右子树这是一棵二叉搜索树，右边的值都比左边大。我们要按从大到小的顺序访问，所以反中序：先右、再根、最后左。从根 50 出发，先一路往右下扎，去找整棵树最大的那个节点。
5去往更大的 70还轮不到 50，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 70，那边的值都比 50 大。
6去往更大的 80还轮不到 70，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 80，那边的值都比 70 大。
7sum 0 + 80 = 8080 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 80 加进累加和：0 加 80 等于 80。此刻 sum 里装的，就是所有不小于 80 的节点值之和。
8节点值 80 → 8080 是整棵树最大的值，没有比它更大的节点，sum 就等于它自己，回填后还是 80。
9sum 80 + 70 = 15070 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 70 加进累加和：80 加 70 等于 150。此刻 sum 里装的，就是所有不小于 70 的节点值之和。
10节点值 70 → 150把当前节点的值改写成 sum，也就是从 70 变成 150。比 70 大的节点早就加进 sum 了，所以这个 150 正是它该有的更大和。
11去往更小的 6070 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 60，它比 70 小。注意 sum 不清零，继续往下累加。
12sum 150 + 60 = 21060 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 60 加进累加和：150 加 60 等于 210。此刻 sum 里装的，就是所有不小于 60 的节点值之和。
13节点值 60 → 210把当前节点的值改写成 sum，也就是从 60 变成 210。比 60 大的节点早就加进 sum 了，所以这个 210 正是它该有的更大和。
14sum 210 + 50 = 26050 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 50 加进累加和：210 加 50 等于 260。此刻 sum 里装的，就是所有不小于 50 的节点值之和。
15节点值 50 → 260把当前节点的值改写成 sum，也就是从 50 变成 260。比 50 大的节点早就加进 sum 了，所以这个 260 正是它该有的更大和。
16去往更小的 3050 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 30，它比 50 小。注意 sum 不清零，继续往下累加。
17去往更大的 40还轮不到 30，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 40，那边的值都比 30 大。
18sum 260 + 40 = 30040 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 40 加进累加和：260 加 40 等于 300。此刻 sum 里装的，就是所有不小于 40 的节点值之和。
19节点值 40 → 300把当前节点的值改写成 sum，也就是从 40 变成 300。比 40 大的节点早就加进 sum 了，所以这个 300 正是它该有的更大和。
20sum 300 + 30 = 33030 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 30 加进累加和：300 加 30 等于 330。此刻 sum 里装的，就是所有不小于 30 的节点值之和。
21节点值 30 → 330把当前节点的值改写成 sum，也就是从 30 变成 330。比 30 大的节点早就加进 sum 了，所以这个 330 正是它该有的更大和。
22去往更小的 2030 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 20，它比 30 小。注意 sum 不清零，继续往下累加。
23sum 330 + 20 = 35020 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 20 加进累加和：330 加 20 等于 350。此刻 sum 里装的，就是所有不小于 20 的节点值之和。
24节点值 20 → 350把当前节点的值改写成 sum，也就是从 20 变成 350。比 20 大的节点早就加进 sum 了，所以这个 350 正是它该有的更大和。
25答案 = [260,330,150,350,300,210,80]反中序访问顺序是 80、70、60、50、40、30、20，sum 一路累加成 80、150、210、260、300、330、350，依次回填到各节点。最大的 80 还是 80，最小的 20 收齐了所有节点变成 350。一遍 DFS 就把整棵树改成了更大和树。

⚠️ 容易写错的地方

✗ 错：用普通中序（左、根、右）从小到大走

✓ 对：要反中序（右、根、左）从大到小走

从小到大走，访问到某点时比它大的还没加进 sum，回填就是错的

✗ 错：每访问一个节点就把 sum 清零

✓ 对：sum 全程只增不清零

sum 要持续累积「比当前更大的所有值」，清零会丢掉前面的累加

✗ 错：先回填再加（顺序反了）

✓ 对：必须先 sum 加原值，再回填

先回填会用旧 sum 覆盖节点，少加了它自己这一份

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int s = 0;
        function<void(TreeNode*)> dfs = [&]( TreeNode* root ) {
            if (!root) {
                return;
            }
            dfs(root->right);
            s += root->val;
            root->val = s;
            dfs(root->left);
        };
        dfs(root);
        return root;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int s;

    public TreeNode bstToGst(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        s += root.val;
        root.val = s;
        dfs(root.left);
    }
}

复杂度

时间

O(n)

反中序遍历每个节点恰好访问一次，每次只做一次加法和一次赋值

空间

O(h)

递归栈深 = 树高 h；平衡时约 O(log n)，最坏退化成链时 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着从二叉搜索树到更大和树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这题和 538「把二叉搜索树转换为累加树」是不是一样？+

完全一样，是同一道题的两个编号，做法一字不差：反中序遍历加累加回填。题面里也明确标注了这点。

如果不是 BST，是普通二叉树呢？+

那反中序就不再是降序了，不能直接累加。要先收集所有节点值，对每个节点单独求「大于等于它的值之和」，或者排序后用前缀和辅助，时间会上升。BST 的好处正是反中序天然降序，一遍就够。

能不能不用递归、把空间压到 O(1)？+

可以用栈做迭代版的反中序，空间仍是 O(h)；想做到 O(1) 可以用 Morris 反中序遍历，靠临时改指针在遍历后还原，面试讲清思路即可。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把从二叉搜索树到更大和树一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1038中等树 · BST

从二叉搜索树到更大和树图解题解

这道题到底在问什么

输入: root=[50,30,70,20,40,60,80]
输出: [260,330,150,350,300,210,80]

最优解：一步一步想明白

3记住这套「右根左降序、sum 先加原值、再把 sum 回填」，下面每帧都在套它。
4从根 50 先扎向右子树这是一棵二叉搜索树，右边的值都比左边大。我们要按从大到小的顺序访问，所以反中序：先右、再根、最后左。从根 50 出发，先一路往右下扎，去找整棵树最大的那个节点。
5去往更大的 70还轮不到 50，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 70，那边的值都比 50 大。
6去往更大的 80还轮不到 70，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 80，那边的值都比 70 大。
7sum 0 + 80 = 8080 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 80 加进累加和：0 加 80 等于 80。此刻 sum 里装的，就是所有不小于 80 的节点值之和。
8节点值 80 → 8080 是整棵树最大的值，没有比它更大的节点，sum 就等于它自己，回填后还是 80。
9sum 80 + 70 = 15070 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 70 加进累加和：80 加 70 等于 150。此刻 sum 里装的，就是所有不小于 70 的节点值之和。
10节点值 70 → 150把当前节点的值改写成 sum，也就是从 70 变成 150。比 70 大的节点早就加进 sum 了，所以这个 150 正是它该有的更大和。
11去往更小的 6070 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 60，它比 70 小。注意 sum 不清零，继续往下累加。
12sum 150 + 60 = 21060 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 60 加进累加和：150 加 60 等于 210。此刻 sum 里装的，就是所有不小于 60 的节点值之和。
13节点值 60 → 210把当前节点的值改写成 sum，也就是从 60 变成 210。比 60 大的节点早就加进 sum 了，所以这个 210 正是它该有的更大和。
14sum 210 + 50 = 26050 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 50 加进累加和：210 加 50 等于 260。此刻 sum 里装的，就是所有不小于 50 的节点值之和。
15节点值 50 → 260把当前节点的值改写成 sum，也就是从 50 变成 260。比 50 大的节点早就加进 sum 了，所以这个 260 正是它该有的更大和。
16去往更小的 3050 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 30，它比 50 小。注意 sum 不清零，继续往下累加。
17去往更大的 40还轮不到 30，因为比它大的右子树还没处理。反中序先吃大的，沿右边往下走到右孩子 40，那边的值都比 30 大。
18sum 260 + 40 = 30040 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 40 加进累加和：260 加 40 等于 300。此刻 sum 里装的，就是所有不小于 40 的节点值之和。
19节点值 40 → 300把当前节点的值改写成 sum，也就是从 40 变成 300。比 40 大的节点早就加进 sum 了，所以这个 300 正是它该有的更大和。
20sum 300 + 30 = 33030 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 30 加进累加和：300 加 30 等于 330。此刻 sum 里装的，就是所有不小于 30 的节点值之和。
21节点值 30 → 330把当前节点的值改写成 sum，也就是从 30 变成 330。比 30 大的节点早就加进 sum 了，所以这个 330 正是它该有的更大和。
22去往更小的 2030 自己回填完了，标成蓝色。反中序最后一步是左子树，走向左孩子 20，它比 30 小。注意 sum 不清零，继续往下累加。
23sum 330 + 20 = 35020 的右子树（比它大的那些）已经全部访问完了，现在轮到它。把它的原值 20 加进累加和：330 加 20 等于 350。此刻 sum 里装的，就是所有不小于 20 的节点值之和。
24节点值 20 → 350把当前节点的值改写成 sum，也就是从 20 变成 350。比 20 大的节点早就加进 sum 了，所以这个 350 正是它该有的更大和。
25答案 = [260,330,150,350,300,210,80]反中序访问顺序是 80、70、60、50、40、30、20，sum 一路累加成 80、150、210、260、300、330、350，依次回填到各节点。最大的 80 还是 80，最小的 20 收齐了所有节点变成 350。一遍 DFS 就把整棵树改成了更大和树。

⚠️ 容易写错的地方

✗ 错：用普通中序（左、根、右）从小到大走

✓ 对：要反中序（右、根、左）从大到小走

从小到大走，访问到某点时比它大的还没加进 sum，回填就是错的

✗ 错：每访问一个节点就把 sum 清零

✓ 对：sum 全程只增不清零

sum 要持续累积「比当前更大的所有值」，清零会丢掉前面的累加

✗ 错：先回填再加（顺序反了）

✓ 对：必须先 sum 加原值，再回填

先回填会用旧 sum 覆盖节点，少加了它自己这一份

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int s = 0;
        function<void(TreeNode*)> dfs = [&]( TreeNode* root ) {
            if (!root) {
                return;
            }
            dfs(root->right);
            s += root->val;
            root->val = s;
            dfs(root->left);
        };
        dfs(root);
        return root;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int s;

    public TreeNode bstToGst(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        s += root.val;
        root.val = s;
        dfs(root.left);
    }
}

复杂度

时间

O(n)

反中序遍历每个节点恰好访问一次，每次只做一次加法和一次赋值

空间

O(h)

递归栈深 = 树高 h；平衡时约 O(log n)，最坏退化成链时 O(n)

看不够？换成动画再走一遍

看交互动画版 →更多图解题

面试官可能追问

这题和 538「把二叉搜索树转换为累加树」是不是一样？+

完全一样，是同一道题的两个编号，做法一字不差：反中序遍历加累加回填。题面里也明确标注了这点。

如果不是 BST，是普通二叉树呢？+

能不能不用递归、把空间压到 O(1)？+

可以用栈做迭代版的反中序，空间仍是 O(h)；想做到 O(1) 可以用 Morris 反中序遍历，靠临时改指针在遍历后还原，面试讲清思路即可。

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

从二叉搜索树到更大和树 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

从二叉搜索树到更大和树 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

从二叉搜索树到更大和树图解题解

从二叉搜索树到更大和树图解题解