Distribute Coins in Binary Tree Solutions in C++

// Source : https://leetcode.com/problems/distribute-coins-in-binary-tree/
// Author : Hao Chen
// Date   : 2019-03-29



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int distributeCoins(TreeNode* root) {
        int result = 0;
        dfs(root, result);
        return result;
    }

    //
    // if a node has 0 coin, which means one move from its parent.
    //               1 coin, which means zero move from its parent.
    //               N coins, which means N-1 moves to its parent.
    //
    // So, we can simply know, the movement = coins -1.
    // - negative number means the the coins needs be moved in.
    // - positive number means the the coins nees be moved out.
    //
    // A node needs to consider the movement requests from both its left side and right side.
    // and need to calculate the coins after left and right movement.
    //
    // So, the node coins  = my conins - the coins move out + the coins move in.
    //
    // Then we can have to code as below.
    //
    int dfs(TreeNode* root, int& result) {
        if (root == NULL) return 0;

        int left_move = dfs(root->left, result);
        int right_move = dfs(root->right, result);
        result += (abs(left_move) + abs(right_move));

        // the coin after movement: coins = root->val +left_move + right_move
        // the movement needs:  movement = coins - 1
        return root->val + left_move + right_move - 1;
    }
};

/// Source : https://leetcode.com/problems/distribute-coins-in-binary-tree/
/// Author : liuyubobobo
/// Time   : 2019-01-20

#include <iostream>

using namespace std;


/// DFS
/// Time Complexity: O(n)
/// Space Complexity: O(1)

/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {

public:
    int distributeCoins(TreeNode* root) {

        int res = 0;
        dfs(root, res);
        return res;
    }

private:
    int dfs(TreeNode* node, int& res){

        if(!node) return 0;

        int l = dfs(node->left, res);
        int r = dfs(node->right, res);
        res += abs(l) + abs(r);
        return node->val + l + r - 1;
    }
};


int main() {

    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(0);
    root->right = new TreeNode(0);
    cout << Solution().distributeCoins(root) << endl;
    // 2

    // [5,0,0,null,null,0,0,3,null,null,0,null,null,null,0]
    // 13

    // [3,null,0,0,null,0,null,2]
    // 4

    // [0,2,3,0,0,null,null,1]
    // 5

    return 0;
}