LEETCODE ALGORITHM:979. Distribute Coins in Binary Tree

发表于 更新于 分类于 Waline： 阅读次数：

题目

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:

img

1
2
3
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:

img

1
2
3
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:

img

1
2
Input: [1,0,2]
Output: 2

Example 4:

img

1
2
Input: [1,0,0,null,3]
Output: 4

Note:

  1. 1<= N <= 100
  2. 0 <= node.val <= N

题解

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int ans;
    int dfs(TreeNode* root)
    {
        if(root==NULL) return 0;
        int l=dfs(root->left);
        int r=dfs(root->right);
        ans+=abs(l)+abs(r);
        return root->val+l+r-1;
    }
public:
    int distributeCoins(TreeNode* root) {
        ans=0;
        dfs(root);
        return ans;

    }
};

算法很巧妙，采用后序遍历从叶子节点开始，因为叶子只能从父节点拿硬币或向父节点送硬币，计算需要拿或送多少硬币，左右节点的需要拿或送硬币的和即为父节点需要硬币的进出状态，而所有拿或送硬币的数量即为答案，因为用正负来区分是取还是送，所以计算传递次数时要加绝对值。