REVISIT: topdown

houserobber3.cpp

#include "code.h"
#include "treenode.h"

class Solution {
private:
  map<long, int> memo;

  long left(long i) { return 2 * i + 1; }

  long right(long i) { return 2 * i + 2; }

  // basic recursion
  int compute(TreeNode* root) {
    if (!root) return 0;
    return max(root->val +
                   ((root->left)
                        ? compute(root->left->left) + compute(root->left->right)
                        : 0) +
                   ((root->right) ? compute(root->right->left) +
                                        compute(root->right->right)
                                  : 0),
               compute(root->left) + compute(root->right));
  }

  // recursion with memoization a.k.a bottom-up
  int computev2(TreeNode* root, long nodeNumber) {
    if (!root) return 0;
    if (memo.find(nodeNumber) != memo.end()) return memo.at(nodeNumber);
    memo[nodeNumber] = max(
        root->val +
            ((root->left)
                 ? computev2(root->left->left, left(left(nodeNumber))) +
                       computev2(root->left->right, right(left(nodeNumber)))
                 : 0) +
            ((root->right)
                 ? computev2(root->right->left, left(right(nodeNumber))) +
                       computev2(root->right->right, right(right(nodeNumber)))
                 : 0),
        computev2(root->left, left(nodeNumber)) +
            computev2(root->right, right(nodeNumber)));
    return memo[nodeNumber];
  }

  // iteration a.k.a top-down
  int computev3(TreeNode* root) {}

public:
  int rob(TreeNode* root) { return computev2(root, 0); }
};