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

思路

先用recursive的方法，把数字按从大到小读一遍，每个数字+=上一个数字（即所有比该数字大的数字总和），存进list
在recur一遍，从小到大把val存进每个node

class Solution:
    
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        list = [0]
        self.test(root, list)
        print (list)
        self.setValue(root, list)
        return root
        
    def test(self, root, list):
        if (root):
            self.test(root.right, list)
            list.append(root.val+list[-1])
            self.test(root.left, list)
            
    def setValue(self, root, list):
        if (root):
            self.setValue(root.left, list)
            root.val = list[-1]
            list.pop()
            self.setValue(root.right, list)