https://leetcode.com/problems/distribute-coins-in-binary-tree/

1. Using DFS:

  1. //8 ms    10.7 MB
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     int distributeCoins(TreeNode* root) {
  14.         int result = 0;
  16.         DFS(root, result);
  18.         return result;
  19.     }
  21. private:
  22.     int DFS(TreeNode* root, int& result){
  23.         if(!root) return 0;
  25.         int l = DFS(root->left, result);
  26.         int r = DFS(root->right, result);
  28.         result += abs(l) + abs(r);
  30.         return root->val + l + r - 1;
  32.     }
  34. };