Covered / Uncovered Nodes

• Time : $O(n)$
• Space : $O(h)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void dfs(TreeNode* A, vector<vector<int>>& unc, int d, long long& sum) {
    if(!A) return;
    if(unc.size() == d) unc.emplace_back();
    if(unc[d].size() == 2) unc[d].pop_back();
    unc[d].push_back(A->val);
    sum += A->val;
    dfs(A->left, unc, d + 1, sum);
    dfs(A->right, unc, d + 1, sum);
}
long Solution::coveredNodes(TreeNode* A) {
    vector<vector<int>> unc;
    long long sum = 0;
    dfs(A,unc,0,sum);
    long long u = 0, c = sum;
    for(auto vec : unc) {
        for(auto v : vec) {
            u += v;
            c -= v;
        }
    }
    return abs(u-c);
}