难度: Medium
给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下，二叉搜索树满足下列约束条件：
示例 1：
输入：root = [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]
示例 3：
输入：root = [1,0,2] 输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1] 输出：[7,9,4,10]
提示：
0 和 104 之间。-104 和 104 之间。注意：
运行时间: 31 ms
内存: 18.2 MB
# 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 convertBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
nonlocal s
if root is None:
return
dfs(root.right)
s += root.val
root.val = s
dfs(root.left)
s = 0
dfs(root)
return root
这个题解采用了递归的方法来实现二叉搜索树到累加树的转换。首先，定义了一个辅助函数 dfs，它采用反向中序遍历（即先访问右子树，再访问根节点，最后访问左子树）。在访问每个节点时，维护一个累加变量 s，这个变量保存了当前已访问节点的值的总和。当访问到一个节点时，将它的节点值更新为 s 加上该节点原始的值。由于二叉搜索树的特性，这种遍历顺序保证了每个节点可以直接获取到所有大于等于它的节点值的总和。
时间复杂度: O(n)
空间复杂度: O(n) in the worst case, O(log n) in the average case
# 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 convertBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
nonlocal s # 使用 nonlocal 关键字，以便在 dfs 函数内修改外部变量 s
if root is None:
return
dfs(root.right) # 先递归处理右子树
s += root.val # 更新累加和
root.val = s # 将当前节点的值更新为累加和
dfs(root.left) # 再递归处理左子树
s = 0 # 初始化累加和为0
dfs(root) # 从根节点开始递归
return root
在此算法中，目的是将每个节点的值更新为原树中所有大于或等于该节点值的所有节点值之和。二叉搜索树的特性是任何节点的右子节点都大于该节点，左子节点都小于该节点。使用反向中序遍历（先访问右子树，再访问节点本身，最后访问左子树）可以确保在处理当前节点之前，已经处理了所有值更大的节点，从而可以直接累加到当前节点的值上。反之，正向中序遍历先处理所有较小的节点，不符合累加树的要求。
如果不使用nonlocal关键字，s变量将不会在递归调用之间正确传递其值，因为每次递归调用都会尝试在本地作用域内定义一个新的s，从而导致无法累积之前的值。替代的实现方式有两种：一是使用类属性来替代局部变量s，这样s的值就可以在所有实例方法之间共享。二是可以将s作为参数传递给递归函数，并在每次递归调用时返回更新后的s值，从而实现累加和的传递。
在递归函数中，如果二叉搜索树为null，直接返回None是处理递归边界条件的标准方法，它可以避免对null节点进行操作导致错误。从设计和安全性角度来看，这种处理方式可以确保函数的健壮性。在此算法中，返回None主要是为了终止递归，避免对不存在的节点进行进一步的处理，这是正确且必要的。没有特别的潜在问题，只要在递归调用之前正确检查节点是否为null即可。