979. 在二叉树中分配硬币 - Kotlin 深度优先搜索 递归

原题地址：https://leetcode.cn/problems/distribute-coins-in-binary-tree/description/

题解

参照题解思路

设函数dfs(root)返回的是以root为根节点的子树富裕/缺少的硬币数量，正数为富裕量，负数为缺少量，且多余的硬币资源已经集中在root上

对于root的子节点

• 当子节点有富裕时，子节点的所有硬币需要经过一步集中在root上等待下一步分配
• 当子节点有缺少时，root节点上的硬币需要经过一步分配到子节点上等待下一步分配

因此对于root节点而言，硬币的移动次数move=dfs(root.left)+dfs(root.right)

当返回时，root这颗子树的总硬币数量为：左子树的富裕量/缺少量+右子树的富裕量/缺少量+root本身的硬币数量-1（因为要减去root本身留下来的一个）

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    var move = 0
    fun distributeCoins(root: TreeNode?): Int {
        dfs(root)
        return move
    }

    fun dfs(root: TreeNode?): Int {
        if (root == null) {
            return 0
        } else {
            move += Math.abs(dfs(root.left))
            move += Math.abs(dfs(root.right))
            return dfs(root.left) + dfs(root.right) + root.`val` - 1
        }
    }
}