0538._Convert_BST_to_Greater_Tree.md

538. Convert BST to Greater Tree

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/convert-bst-to-greater-tree/

内容描述

Given 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.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

先inorder遍历成功后，求后缀和数组，更新每个node的value为后缀和数组中对应index的值

beats 54.49%

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def inorder(root):
            if not root:
                return []
            res = []
            return inorder(root.left) + [root] + inorder(root.right)
        
        if not root:
            return None
        nodes = inorder(root)
        values = [node.val for node in nodes]
        suffix = [values[-1]] * len(values)
        for i in range(len(suffix)-2, -1, -1):
            suffix[i] = suffix[i+1] + values[i]
        for idx, node in enumerate(nodes):
            node.val = suffix[idx]
        return root