问题描述
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)