979. Distribute Coins in Binary Tree

T: O(n)
S: O(n)

硬币的移动规则看似很复杂，因为一个节点可能需要移出硬币，也可能移入硬币，还要求移动次数最少。实际上我们需要观察规律，做一些等价。

如果一个节点的硬币个数是 x，无论是移出还是移入，把该节点的硬币个数变成 1 的最少移动次数必然是 abs(x - 1)。

发现这个规律后，开始二叉树的通用解题思路：假想你现在站在某个根节点上，你如何知道把当前这棵子树的所有节点配平所需的最小移动次数？

那就很简单了，你假想多余的和缺少的硬币都移动到根节点去配平，当然根节点本身也要配平，所以整棵树配平的移动次数就是：

// 让当前这棵树平衡所需的移动次数
Math.abs(left) + Math.abs(right) + (root.val - 1);
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int distributeCoins(TreeNode root) {
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    private int dfs(TreeNode node, int[] result) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left, result);
        int right = dfs(node.right, result);
        // System.out.println(left);
        // System.out.println(right);
        // System.out.println(Math.abs(left) + Math.abs(right) + node.val - 1);
        result[0] += Math.abs(left) + Math.abs(right) + node.val - 1; // move times, so need abs
        return left + right + node.val - 1;
    }
}

/***
ex:
  3 
 0. 
0

left = 0
right = 0
result += (Math.abs(left) + Math.abs(right) + node.val - 1) = 0 + 0 + (0-1) = -1
return -1

-> result[0] = -1;

left = -1
right = 0
result += (Math.abs(left) + Math.abs(right) + node.val - 1) = 1 + 0 + (0-1) = 0
return -2
-> result[0] = -1;

left = 2
right = 0
result += (Math.abs(left) + Math.abs(right) + node.val - 1) = 2 + 0 + (3-1) = 4
return 
 -> result[0] = -1 + 4 = 3;
 so 3 moves



T: O(n)
S: O(n) 


 */

Another easy thought:

Latest

Previous814. Binary Tree PruningNext1325. Delete Leaves With a Given Value

Last updated

Was this helpful?