【leetcode】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.

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

解题思路：一时卡壳了，只想出了一个很挫的方法，把所有节点的值都取出来，然后找出每个节点的所有比其大的值的和，这个值就是这个节点的值要加上的大小，最后再遍历一次树修改节点。

代码如下：

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

class Solution(object):
    l = []
    dic = {}
    def traverse(self,node,mode):
        if node == None:
            return
        if mode == 1:
            self.l.append(node.val)
        else:
            node.val += self.dic[node.val]
        if node.left != None:
            self.traverse(node.left,mode)
        if node.right != None:
            self.traverse(node.right,mode)


    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.l = []
        self.dic = {}
        self.traverse(root,1)
        ul = sorted(list(set(self.l)))
        total = 0
        for i in ul[::-1]:
            self.dic[i] = total
            total += i
        self.traverse(root, 0)
        return root