LeetCode之Binary Search Tree to Greater Sum Tree（Kotlin）

2019-09-06 227 阅读1分钟

问题：

方法：通过DFS递归遍历，中序遍历；对先遍历的节点进行求和，所有节点的值都等于原有值加已求和值，最后输出根节点即为最终结果。

具体实现：

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

    private var gst = 0

    fun bstToGst(root: TreeNode?): TreeNode? {
        gst = 0
        dfs(root)
        return root
    }

    private fun dfs(root: TreeNode?) {
        if (root == null) {
            return
        }
        dfs(root.right)
        root.`val` += gst
        gst = root.`val`
        dfs(root.left)
    }
}

有问题随时沟通

具体代码实现可以参考Github