leetcode#递归#979. 在二叉树中分配硬币_给定一个有 n 个结点的二叉树根结点 root,树中的每个结点上都对应有 node.val 枚

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。

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

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int distributeCoins(TreeNode root) {
        op.dfs(root);
        return op.count;
    }
    Op op = new Op();

    static class Op{
        int count;



        int  dfs(TreeNode root) {
            if(root == null) return 0;
            int leftCount = dfs(root.left);
            int rightCount = dfs(root.right);
            count+= Math.abs(leftCount)+ Math.abs(rightCount);
            // 返回当前节点
            return leftCount+rightCount-1+ root.val;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31