###### tags: `Leetcode` `medium` `tree` `python` `c++`

# 538. Convert BST to Greater Tree

## [題目連結:] https://leetcode.com/problems/convert-bst-to-greater-tree/description/

## 題目:
Given the ```root``` of 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 the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

* The left subtree of a node contains only nodes with keys **less than** the node's key.
* The right subtree of a node contains only nodes with keys **greater than** the node's key.
* Both the left and right subtrees must also be binary search trees.


## 解題想法:
* 此題為給一BST，對於每點，將所以比該點大的值，都加到該點上
* ex: 4: 比他大的為5+6+7+8共26 所以4更新為30

* 想法:
* **逆向中序遍歷**
* 依序遍歷: **右中左** 則最先遍歷到的點一定是最大的
* 將其值依序累加，逐一更新所有點

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        #所有比該點大的值 都加到該點上
        #逆向中序: 遍歷 右中左 
        #將其值往後加 依序更新所有點
        self.sum=0
        self.dfs(root)
        return root
    def dfs(self,root):
        if not root:
            return 
        self.dfs(root.right)
        root.val+=self.sum
        self.sum=root.val
        self.dfs(root.left)

root=TreeNode(4)
root.insertLeft(1)
root.insertRight(6)
root.left.insertLeft(0)
root.left.insertRight(2)
root.left.right.insertRight(3)
root.right.insertLeft(5)
root.right.insertRight(7)
root.right.right.insertRight(8)
print("Original:",end='')
root.printTree()

result=Solution()
ans=result.convertBST(root)
print("After:",end='')
root.printTree()

## C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode* root){
        if (!root)
            return ;
        dfs(root->right);
        root->val+=sum;
        sum=root->val;
        dfs(root->left);
    }
private:
    int sum=0;
};