leetcode 979. Distribute Coins in Binary Tree二叉树中分硬币_综合

题目要求

题目给出了一个二叉树，每个节点都有个数字并且这个数字代表当前节点有多少个金币，所有节点的金币数量之和等于节点总个数（即N个节点一共有N个金币）。现在要求把金币平分到每个节点，使得每个节点都只放1个金币。问需要的移动次数是多少？
在这里插入图片描述

题解思路

递归思路，深度优先遍历，每个节点保证含有一个金币，换句话说，如果当前结点含有m个节点，那么那就要移动m-1步。可以拆分成左右节点来看，总的移动次数就是左树+右树（绝对值操作，毕竟若当前节点没有金块，那么0-1=-1，也需要移动一次给当前结点）。

总结一句话：对于当且节点的移动次数 m-1 + left + right

主要代码c++

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
// helper dfs 遍历到底
class Solution {
    
public:int res = 0;int distributeCoins(TreeNode* root) {
    dfs(root);return res;}int dfs(TreeNode* root){
    if(root == NULL) return 0;int left = dfs(root->left);int right = dfs(root->right);res += abs(left) + abs(right);return root->val - 1 + left + right;}
};