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

每个节点要变成哪些值的和

给一棵二叉搜索树，也就是左小右大的那种树 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 盖掉原值，它自己那份反倒少算。

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);
    }
}