LeetCode之Convert BST to Greater

问题：
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.

方法：
BST特性是右节点一定大于根节点，左节点一定小于根节点；通过递归的方式，先遍历右子树，求右子树所有节点值的和，根节点的值就等于当前值加右子树的和；同理，遍历左子树时，左子树节点的值等于当前值加上其所有父级节点及父节点右子树的和。

具体实现：

class ConvertBSTtoGreaterTree {
    var sum = 0
    class TreeNode(var `val`: Int = 0) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }

    fun convertBST(root: TreeNode?): TreeNode? {
        if(root == null) {
            return null
        }
        convertBST(root.right)
        root.`val` += sum
        sum = root.`val`
        convertBST(root.left)
        return root
    }

    companion object {
        fun dfs(root: TreeNode?) {
            if (root == null) {
                return
            }
            print("${root?.`val`}  ")
            dfs(root.left)
            dfs(root.right)
        }
    }
}

fun main(args: Array<String>) {
    val root = ConvertBSTtoGreaterTree.TreeNode(4)
    root.left = ConvertBSTtoGreaterTree.TreeNode(2)
    root.right = ConvertBSTtoGreaterTree.TreeNode(8)
    (root.left)?.left = ConvertBSTtoGreaterTree.TreeNode(1)
    (root.left)?.right = ConvertBSTtoGreaterTree.TreeNode(3)
    (root.right)?.right = ConvertBSTtoGreaterTree.TreeNode(9)
    val convertBSTtoGreaterTree = ConvertBSTtoGreaterTree()
    val result = convertBSTtoGreaterTree.convertBST(root)
    ConvertBSTtoGreaterTree.dfs(result)
    println()
}

有问题随时沟通

具体代码实现可以参考Github