Comment on page

979.Distribute-Coins-in-Binary-Tree

979. Distribute Coins in Binary Tree

题目地址

题目描述

Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.
​
In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)
​
Return the number of moves required to make every node have exactly one coin.
​
Example 1:
Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
​
Example 2:
Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
​
Example 3:
Input: [1,0,2]
Output: 2
​
Example 4:
Input: [1,0,0,null,3]
Output: 4
​
Note:
1<= N <= 100
0 <= node.val <= N

代码

Approach #1 DFS

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int ans;
public int distributeCoins(TreeNode root) {
ans = 0;
dfs(root);
return ans;
}
​
public int dfs(TreeNode node) {
if (node == null) return 0;
int L = dfs(node.left);
int R = dfs(node.right);
ans += Math.abs(L) + Math.abs(R);
return node.val + L + R - 1;
}
}

Approach #2 Abs(nodes - coins)

Both of these two operations will create moves in the tree. And we just need to add the absolute value of the (# nodes - # coins) to the final result because the move can be "contribute" or "take". The time complexity is O(n) because we are just traversing the tree.
class Solution {
int moves = 0;
public int distributeCoins(TreeNode root) {
getNumAndCoins(root);
return moves;
}
​
/*
* return [number_of_nodes_in_subtree, number_of_total_coins_in_subtree]
*/
private int[] getNumAndCoins(TreeNode node) {
if (node == null) return new int[] {0, 0};
int[] left = getNumAndCoins(node.left);
int[] right = getNumAndCoins(node.right);
moves += Math.abs(left[0] - left[1]) + Math.abs(right[0] - right[1]);
return new int[] {left[0] + right[0] + 1, left[1] + right[1] + node.val};
}
}