LeetCode 979. 在二叉樹中配置設定硬币（DFS）

1. 題目

給定一個有 N 個結點的二叉樹的根結點 root，樹中的每個結點上都對應有 node.val 枚硬币，并且總共有 N 枚硬币。

在一次移動中，我們可以選擇兩個相鄰的結點，然後将一枚硬币從其中一個結點移動到另一個結點。(移動可以是從父結點到子結點，或者從子結點移動到父結點。)。

傳回使每個結點上隻有一枚硬币所需的移動次數。

輸入：[3,0,0]
輸出：2
解釋：從樹的根結點開始，我們将一枚硬币移到它的左子結點上，一枚硬币移到它的右子結點上。           

複制

輸入：[0,3,0]
輸出：3
解釋：從根結點的左子結點開始，我們将兩枚硬币移到根結點上 [移動兩次]。然後，我們把一枚硬币從根結點移到右子結點上。           

複制

輸入：[1,0,2]
輸出：2           

複制

輸入：[1,0,0,null,3]
輸出：4
 
提示：
1<= N <= 100
0 <= node.val <= N           

複制

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/distribute-coins-in-binary-tree

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. DFS 解題

• 對于一個葉子節點，需要移動的次數是

  abs(val-1)

• 對于一個節點的子樹而言，需要的金币移動次數等于

  abs(Σ(val_i-1))

class Solution {
	int move = 0;
public:
    int distributeCoins(TreeNode* root) {
        dfs(root);
        return move;
    }

    int dfs(TreeNode* root)
    {
    	if(root == NULL)
    		return 0;
    	int l = dfs(root->left);
    	int r = dfs(root->right);
		move += abs(l)+abs(r);
    	return l+r+root->val-1;
    }
};           

複制