Distribute Coins in Binary Tree
给一个二叉树, 然后给一个node的值是coin的数量, 求把这个coins分给每个node需要几步, 一步只能往下推一个node.
这题就是divide and conquer, 例题给的很明确, 如果是root有3个, 左右是0, 那么分下去需要2步(给左边一个, 给右边一个), 这题还给了一共n个node和n个coin, 所以不存在溢出的情况. 所以只需要计算left和right的和-1 就是需要的步骤.
|
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 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int res = 0; int distributeCoins(TreeNode* root) { dfs(root); return res; } int dfs(TreeNode* root){ if(!root) return 0; int l = dfs(root->left); int r = dfs(root->right); res += abs(l) + abs(r); return root->val + l + r - 1; //1 for itself } }; |