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
难度
Medium
方法
对二叉树进行相反的前序遍历，即按照右节点-根节点-左节点的顺序遍历，这样就是从大到小的顺序遍历节点。然后用一个变量比如basic保存需要加到节点上的值，最后更新节点值即可
python代码
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def __init__(self):
self.basic = 0
def convertBST(self, root):
if root:
self.traverse(root)
return root
def traverse(self, node):
if node.right:
self.traverse(node.right)
self.basic += node.val
node.val = self.basic
if node.left:
self.traverse(node.left)
root = TreeNode(5)
root.left = TreeNode(2)
root.right = TreeNode(13)
root = Solution().convertBST(root)
assert root.val == 18
assert root.left.val == 20
