文章收录网站,黑马培训,wordpress模板带数据库,wordpress图片搬家给你一个有 n 个结点的二叉树的根结点 root #xff0c;其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。
在一次移动中#xff0c;我们可以选择两个相邻的结点#xff0c;然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到…给你一个有 n 个结点的二叉树的根结点 root 其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。
在一次移动中我们可以选择两个相邻的结点然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点或者从子结点移动到父结点。
返回使每个结点上 只有 一枚硬币所需的 最少 移动次数。 每个硬币移动一次就会经过一条边 原问题可用转换为 所有边被经过的次数之和。
二叉树中每一条边会连接一个子树这个子树多的硬币会经过这条边少的硬币会从其他地方运到该子树。
所以每个边被经过的次数就是该边对应的子树中 节点个数 和 金币个数之差 的绝对值。
可以使用dfs来做。 vectorintdfs(node *root)表示以root为根节点的树中 节点个数 和 金币个数 v[0]表示节点个数v[1]表示金币个数。 vectorintdfs(root): vectorintv,left,right; if(root-left) left dfs (root-left)res abs(left[0]-left[1]); if(root-right) right dfs (root-right); res abs(right[0]-right[1]); v[0]left[0]right[0]1; v[1]left[1]right[1]root-val; return v; class Solution {
public: int res0;vectorintdfs(TreeNode *root){vectorintv(2,0);vectorintleft(2,0);vectorintright(2,0); if(root-left){left dfs(root-left);}if(root-right){right dfs(root-right); }res abs(left[0]-left[1]);res abs(right[0]-right[1]);v[0]left[0]right[0]1;v[1]left[1]right[1]root-val;return v;}int distributeCoins(TreeNode* root) {dfs(root);return res;}
};
