[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

难度

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