题目
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees. Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
解题思路
使用右根左的顺序遍历，遍历的时候记录所有经过节点的总和，更新当前节点
代码
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
if not root:
return
dfs(root.right)
self.ct += root.val
root.val = self.ct
dfs(root.left)
self.ct = 0
dfs(root)
return root
