問(wèn)題描述

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的方法，把數(shù)字按從大到小讀一遍，每個(gè)數(shù)字+=上一個(gè)數(shù)字（即所有比該數(shù)字大的數(shù)字總和），存進(jìn)list
在recur一遍，從小到大把val存進(jìn)每個(gè)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)