【二叉树】在二叉树中分配硬币

0x00 题目

给定一个有 N 个结点的二叉树的根结点 root
树中的每个结点上都对应有 node.val 枚硬币
并且总共有 N 枚硬币

在一次移动中，我们可以选择两个相邻的结点
然后将一枚硬币从其中一个结点移动到另一个结点
移动可以是从父结点到子结点，或者从子结点移动到父结点

返回使每个结点上只有一枚硬币所需的移动次数

---

0x01 思路

每个节点都需要有一枚硬币
所以节点 r 所需的硬币是 r.val - 1
r.val > 1 时
说明要把多余的硬币移走
r.val == 0 时
说明需要从别的地方移入硬币
以 r 为根的节点
所需的总硬币数为
r.val - 1 + 左子树所需 + 右子树所需

所以需要使用后序遍历方式

---

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func distributeCoins(_ root: TreeNode?) -> Int {
    var res = 0
    
    func need(_ root: TreeNode?) -> Int {
        guard let r = root else { return 0 }
        
        // 左子树
        let left = need(r.left)
        
        // 右子树
        let right = need(r.right)
        
        // 以 r 为根节点的子树，总共所需的移动次数
        res += abs(left) + abs(right) + r.val - 1
        
        // 当前树所需要的硬币数，正，移出，负，移入
        let out = left + right + r.val - 1
        
        return out
    }
    
    _ = need(root)
    
    return res
}

---

0x03 我的作品

欢迎体验我的作品之一：小五笔 86 版
五笔学习好帮手~
App Store 搜索即可~

---