leetcode

0 class Solution {

1 public:

2 int distributeCoins(TreeNode *root) {

3 TreeNode dummy(0);

4 stack<pair<TreeNode *, TreeNode *>> q({{root, &dummy}});

5

6 int res = 0;

7 while (!q.empty()) {

8 auto [root, parent] = q.top();

9 if (root) {

10 q.push({nullptr, nullptr});

11 if (root->left) q.push({root->left, root});

12 if (root->right) q.push({root->right, root});

13 continue;

14 }

15 q.pop();

16 tie(root, parent) = q.top();

17 q.pop();

18 parent->val += root->val - 1;

19 res += abs(root->val - 1);

20 }

21

22 return res;

23 }

24 };