979. 在二叉树中分配硬币

书籍是一把利斧，凿开我们内心冰封的海洋。

参考979. 在二叉树中分配硬币，难度分1709。

题目

给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。

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

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

输入：root = [3,0,0]
输出：2
解释：一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。

输入：root = [0,3,0]
输出：3
解释：将两枚硬币从根结点的左子结点移动到根结点（两次移动）。然后，将一枚硬币从根结点移动到右子结点。

解题思路

• 递归/深度优先搜索：考虑递归处理,流程为子节点计算差值后,多的上交给根节点,少的从根节点拿,然后继续递归处理左右子树达到平衡。
• 递归/贡献法：把路径移动次数转化为边的经过次数。

递归

class Solution {
    public int distributeCoins(TreeNode root) {
        //考虑递归
        if(root == null) return 0;
        //计算节点数
        int lc = getCount(root.left),rc = getCount(root.right);
        int lv = getVal(root.left),rv = getVal(root.right);
        //判断是否需要经过根节点
        int min = 0;
        //多的运到根节点
        if(lc < lv) {
            root.left.val -= lv-lc;
            //root.val += lv-lc;
            min += lv-lc; 
        }
        if(rc < rv) {
            root.right.val -= rv-rc;
            //root.val += rv-rc;
            min += rv-rc; 
        }
        //少的从根节点拿
        if(lc > lv) {
            root.left.val += lc-lv;
            //root.val -= lc-lv;
            min += lc-lv; 
        }
        if(rc > rv) {
            root.right.val += rc - rv;
            //root.val -= rc - rv;
            min += rc - rv;
        }
        //此时两边节点相同 递归处理左右子树
        return min + distributeCoins(root.left) + distributeCoins(root.right);
    }

    int getCount(TreeNode node) {
        if(node==null)return 0;
        return 1 + getCount(node.left) + getCount(node.right);
    }
    int getVal(TreeNode node) {
        if(node==null)return 0;
        return node.val + getVal(node.left) + getVal(node.right);
    }
}

递归/贡献法

class Solution {
    int ans;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode node) {
        if (node == null)return 0;
        int d = dfs(node.left) + dfs(node.right) + node.val - 1;
        ans += Math.abs(d);
        return d;
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)，递归栈空间。