Leetcode学習ノート:#979.Distribute Coins in Binary Tree

770 ワード

Leetcode学習ノート:#861.Score After Flipping Matrix
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.
実装:
int res = 0;
public int distributeCoins(TreeNode root){
	dfs(root);
	return res;
}

public int dfs(TreeNode root){
	if(root == null){
		return 0;
	}
	int left = dfs(root.left), right = dfs(root.right);
	res += Math.abs(left) + Math.abs.(right);
	return root.val + left + right -1;
}

考え方:DFS、前序は二叉木を遍歴して、その親ノードに硬貨の数を返します