538. Convert BST to Greater Tree

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

BST性质：比当前node大的数都在右子树，所以每个node都加上右子树的sum就行，添加一个全局变量用来记录right subtree sum，递归遍历。

class Solution:
    def __init__(self):
        self.sumSubtree = 0
        
    def convertBST(self, root: TreeNode) -> TreeNode:
        return self.traversal(root)
        
    def traversal(self, root):
        if not root: return root
        self.convertBST(root.right)
        self.sumSubtree += root.val
        root.val = self.sumSubtree
        self.convertBST(root.left)
        return root