难度: Medium
给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下， 二叉搜索树 满足下列约束条件：
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1] 输出：[1,null,1]
提示：
[1, 100] 范围内。0 <= Node.val <= 100注意：该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/ 相同
运行时间: 23 ms
内存: 15.9 MB
# 定义一个二叉树
# 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: TreeNode) -> TreeNode:
#记录当前节点前面的和
self.pre = 0
return self.sum_btree(root)
def sum_btree(self,node):
#终止条件，输入根节点为空，或者遍历到根节点
if node is None:
return None
#需要倒叙遍历——从大到小，二叉搜索树从小到大是中序遍历左中右，倒叙遍历就是右中左
#右：
self.sum_btree(node.right)
#中：
node.val = node.val + self.pre
self.pre = node.val
#左：
self.sum_btree(node.left)
return node
本题的解决方案基于二叉搜索树（BST）的特性，利用中序遍历的变体来解决问题。传统的中序遍历（左-中-右）可以访问BST中的节点，使节点值按升序排列。为了计算每个节点的新值，需要对所有大于或等于该节点值的节点值进行求和，可以通过反中序遍历（右-中-左）来实现，这样可以从最大的节点开始累加值。具体过程是：从BST的最右侧节点开始遍历，累计过程中将每个节点的值加到一个累积和中，并更新当前节点值为这个累积和。这种方式确保了每个节点在更新其值之前，所有大于该节点的值已被累加到总和中。
时间复杂度: O(n)
空间复杂度: O(h)，其中 h 是树的高度
# 定义一个二叉树
# 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: TreeNode) -> TreeNode:
# 初始化累加和变量
self.pre = 0
# 开始反中序遍历并更新节点值
return self.sum_btree(root)
def sum_btree(self, node):
# 如果节点为空，返回None
if node is None:
return None
# 反中序遍历右子树
self.sum_btree(node.right)
# 更新节点值并累加
node.val += self.pre
self.pre = node.val
# 反中序遍历左子树
self.sum_btree(node.left)
# 返回当前节点，以便上一层递归使用
return node
在本题中，每个节点需要更新为原始节点值加上所有大于该节点的节点值之和。使用反中序遍历（右-中-左）可以确保在访问一个节点之前，已经访问了所有的大于该节点的值。这样，当访问到一个节点时，就可以直接使用之前累加的和（所有访问过的节点的值之和），直接更新当前节点值。如果使用正中序遍历（左-中-右），则需要在访问一个节点后，再去累加所有大于该节点的值，这会复杂和低效，因为还需要存储或重新计算大于当前节点的节点值之和。
该方法并不假设树的结构必须是对称或平衡的。反中序遍历简单地遵循右-中-左的顺序，这保证了无论树的结构如何，总是先访问较大的值。树的结构（如是否平衡）主要影响的是遍历的效率。在极端情况下（如退化成链表的情况），遍历可能导致较高的递归深度，从而影响效率。然而，对于二叉搜索树的修改操作，无论树的形状如何，时间复杂度均为 O(n)，因为每个节点仍需要访问一次。
`self.pre`变量用作全局累加和的存储，其在递归过程中被持续更新，确保每次递归调用时都能够访问到最新的累加值。由于Python的递归调用是基于单线程执行的，不存在线程安全问题。然而，对于非常深的二叉树，递归调用可能导致堆栈溢出。这是递归实现的一个通常风险，可以通过增加递归限制或转换为迭代方式（使用显式堆栈）来解决。
在反中序遍历过程中，因为是从最大的节点开始，逐步累加至最小节点，确保了在更新当前节点值时，所有大于等于该节点的值已经被包括在内。由于每个节点在更新前，其所有大于它的节点已经被访问并累加，因此不会存在漏算的情况。这种方法通过正确的遍历顺序和累加保证了每个节点的新值计算的完整性和正确性。