本文共 748 字，大约阅读时间需要 2 分钟。

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

Example 1:

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

看题介绍不是很明白，不过看图就懂了。就是遍历右子树、根节点、左子树，然后逐步val相加。

用dfs的方法，先遍历右子树，找到最右下角的node，然后再找他的跟节点，然后再遍历左子树。

用sum记录遍历过节点val的和，然后再赋值给当前节点即可。

class Solution:    def bstToGst(self, root: TreeNode) -> TreeNode:        self.sum=0        self.dfs(root)        return root    def dfs(self, root):        if root is None:return root        self.dfs(root.right)        self.sum+=root.val        root.val=self.sum        self.dfs(root.left)

转载地址：http://tjrbb.baihongyu.com/