-
题目链接:
https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/
要求计算得出总共需要多少次移动才能使得每个节点上都有一个硬币。
-
解题思路:
这道题一开始陷入dfs, 根左右, 陷入递归和回朔中，思路就已经错了。无法自拔。看了下题解，其实二叉树的问题就是分解。不断分解子问题。分解过程就是递归过程。然后只需要处理最后根节点即可。
因为是个二叉树, 所以可以当成一个根节点，一个左节点，一个右节点，处理，只要左右两边都处理完了，再去处理根节点(root.val = root.left.val + root.right.val)。这个遍历方式就是后续遍历。
左右节点与根节点的关系, 如果左右节点金币数为x，y。则 移动次数为 |x-1| + |y-1|
代码如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int cnt;
public int distributeCoins(TreeNode root) {
cnt = 0;
dfs(root);
return cnt;
}
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
if (node.left != null) {
node.val += dfs(node.left);
}
if (node.right != null) {
node.val += dfs(node.right);
}
cnt += Math.abs(node.val - 1);
return node.val - 1;
}
}
