538. 把二叉搜索树转换为累加树

一、题目描述

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree），使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路

• 因为是二叉搜索树，所以节点值的大小顺序为左 < 根 < 右
• 大小顺序像极了中序遍历2 5 13
• 就以题目中的二叉搜索树为例，右子树的值13不变，根的值等于5+13=18。左子树节点的值为13+5+2=20，更进一步就是18+2=20。
• 所以中序遍历逆向依次累加，便是结果。

三、代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        '''中序遍历，逆序'''

        def recursion(root):
            nonlocal sums
            if root:
                recursion(root.right)
                sums += root.val
                root.val = sums
                recursion(root.left)

        sums = 0
        recursion(root)

        return root

四、表现

运行时间	击败	内存消耗	击败
88ms	37.41%	15.5MB	47.41%