[979] Distribute Coins in Binary Tree

奇怪～為何只有我寫的好像計算很多? (thinking 圖)

莫非是，下面往上傳的node value 根本不重要嗎 ？！

（但想想好像也是 ？！）

好像比別人寫的醜很多～哈哈哈 （大笑奔入雨中）

int ret;

int dfs(struct TreeNode* root, int curVal)

{

if (root== NULL)

return curVal;

int left=0;

int right=0;

if (root->left != NULL)

left = dfs(root->left, curVal);

if (root->right != NULL)

right = dfs(root->right, curVal);

int check = root->val + left + right;

if (check==1)

return 0;

if (check >1)

{

ret += (check -1);

curVal+= (check -1);

}

else // node->val < 0

{

ret += 1-check;

curVal -= (1-check);

}

return curVal;

}

int distributeCoins(struct TreeNode* root) {

ret = 0;

dfs(root,0);

return ret;

}

結果沒錯, 不需要node value 的回傳!

int dfs(struct TreeNode* root)

{

if (root== NULL)

return 0;

int left=0;

int right=0;

if (root->left != NULL)

left = dfs(root->left);

if (root->right != NULL)

right = dfs(root->right);

ret += abs(left)+ abs(right);

return root->val + left+right -1;

}

int distributeCoins(struct TreeNode* root) {

ret = 0;

dfs(root);

return ret;

}