House Robber III dynamiic programming memoization with tree payloads

house-robber-iii-payload.cpp

struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct Payload {
    int dk, dkb;
};

void compute(TreeNode *n, Payload *p) {
    Payload *pl = 0, *pr = 0;
    TreeNode *nl = n->left, *nr = n->right;
    if (nl) pl = new Payload(), compute(nl, pl);
    if (nr) pr = new Payload(), compute(nr, pr);
    
    p->dk  = n->val + (pl ? pl->dkb : 0) + (pr ? pr->dkb : 0);
    p->dkb = (pl ? max( pl->dk, pl->dkb ) : 0) + (pr ? max( pr->dk, pr->dkb ) : 0);
    
    if (pl) delete pl;
    if (pr) delete pr;
}

int rob(TreeNode* root) {
    if (!root) return 0;
    Payload *proot = new Payload();
    
    compute(root, proot);
    return max(proot->dk, proot->dkb);
}